Easy to Understand | Python | Logically Explained | DP
Pre-Requisites - 0/1 Knapsack\n\nSolution -\nLet\'s do some ground work first.\nFor all the piles we can make them into prefix sum arrays\neg:- [2, 7, 3] -> [0,
**Pre-Requisites - 0/1 Knapsack**\n\n**Solution -**\nLet\'s do some ground work first.\nFor all the piles we can make them into prefix sum arrays\neg:- [2, 7, 3] -> [0, 2, 9, 12]\nNow the question is not how many of elements of each array to take rather which element of each prefix sum array to take.\nAlso, we can associate weights with each element (basically denoting the number of elements taken from that array).\nTaking the previous array, [[0, 0], [2, 1], [9, 2], [12, 3]] - 0, 1, 2, 3 are the number of elements taken\n\nNow, we have to take one of them from each pile and the sum of weights should be k, seems kinda like knapsack, right?\nThe only difference is we can\'t independently take elements as taking [2, 1] & [9, 2] would just mean we\'re taking the element \'2\' twice.\nSo we have to take one element from each pile (more preceisely one element of prefix sum array)\n\nNow this is easily solvable as in 0/1 knapsack, we used to go to the previous row to check the maximum possible answer with remaining weight (column_number - weight) and in this we\'ll go to the last row which contained weights from the previous pile and not the current one (to avoid picking up any weight twice)\n\n**Code -**\n```\nclass Solution:\n    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n        \n        n = len(piles)\n            \n        prefix = []\n        \n        #prev array represents where the elements from last pile ended\n        prev = [0]\n        \n        for pile in piles:\n            curr = [0]\n            for ele in pile:\n                curr.append(curr[-1]+ele)\n            prefix.append(curr)\n            \n            prev.append(prev[-1]+len(pile))\n            \n        dp = [[0]*(k+1) for i in range(prev[-1]+1)]\n            \n        for i in range(n):\n            for j in range(1, len(prefix[i])):\n                \n                profit = prefix[i][j]\n                wt = j\n\n                # lvl represents row number\n                # We\'ve given a different row to every prefix sum array element.   \n                lvl = prev[i]+j \n                \n                for w in range(1, k+1): \n                    if wt > w:\n                        dp[lvl][w] = dp[lvl-1][w]\n                    else:\n                        dp[lvl][w] = max(dp[lvl-1][w], profit+dp[prev[i]][w-wt])\n        return dp[-1][-1]
['Dynamic Programming', 'Python']