Nice DP with O(kn²) complexity

Believe me. This DP problem is a very nice problem. It has some connection to the very classical 0–1 knapsack problem. However, it is not exactly the same. The solution is interesting and here are the detail explanation (from comments of bottom-up approach) and codes.

813. Largest Sum of Averages

https://leetcode.com/problems/largest-sum-of-averages/

Bottom-up solution with explanation

Runtime: 340 ms, faster than 43.48% of Python3 online submissions for Largest Sum of Averages.
Memory Usage: 13.1 MB, less than 100.00% of Python3 online submissions for Largest Sum of Averages

We can also have a top-down approach based on a similar idea.

Runtime: 116 ms, faster than 97.39% of Python3 online submissions for Largest Sum of Averages.
Memory Usage: 13.6 MB, less than 100.00% of Python3 online submissions for Largest Sum of Averages.

From the analysis process of bottom-up, we can see the complexity of this algorithm is the number of states O(nk) by the number of operations for each state. Each state, we get the maximum from about n values, so the complexity for each state of O(n).
The final time complexity will be O(kn²)
Reference
https://leetcode.com/problems/largest-sum-of-averages/discuss/122704/Simple-python-solution