[Python] Bottom-up DP solution
Intuition\nBottom-up dynamic programming.\n\n\nExplanation\nTop-down DP solution is well-explained in @lee215\'s post. Here we present the Bottom-up DP solution
**Intuition**\nBottom-up dynamic programming.\n\n\n**Explanation**\nTop-down DP solution is well-explained in @lee215\'s [post](https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/discuss/1887010/JavaC%2B%2BPython-Top-down-DP-solution). Here we present the Bottom-up DP solution.\n`dp[i][j]` is the maximum total value from `pile[0]` to `pile[i]`, if choosing exactly `j` coins optimally.\nWe can pick `0, 1, 2, 3, ... , len(pile[i])` elements from the current `pile[i]` one by one.\nIt asks for the maximum total value of coins we can have, so we need to return max of all the options.\n\n\n**Complexity**\nTime `O(m * k)`\nSpace `O(n * k)`\nwhere `m = sum(piles[i].length) <= 2000`.\nTime complexity is well-explained in @DBabichev\'s [post](https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/discuss/1886905/Python-dp-solution-(complexity-updated)-explained), don\'t be scared by the triple for-loop here.\n\n\n**Python 3 solution**\n```\nclass Solution:\n    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n        n, m = len(piles), 0\n        prefixSum = []\n        for i in range(n):\n            temp = [0]\n            for j in range(len(piles[i])):\n                temp.append(temp[-1] + piles[i][j])\n                m += 1\n            prefixSum.append(temp)\n        if m == k:\n            return sum(temp[-1] for temp in prefixSum)\n            \n        dp = [[0] * (k + 1) for _ in range(n)]\n        for j in range(1, k + 1):\n            if j < len(prefixSum[0]):\n                dp[0][j] = prefixSum[0][j]\n        \n        for i in range(1, n):\n            for j in range(1, k + 1):\n                for l in range(len(prefixSum[i])):\n                    if l > j:\n                        break\n                    dp[i][j] = max(dp[i][j], prefixSum[i][l] + dp[i - 1][j - l])\n        return dp[n - 1][k]\n```\nPlease upvote if you find this solution helpful.
['Dynamic Programming', 'Python', 'Python3']