prefix sum + 2d DP
Intuition\nUse DP and prefix sum\n\n# Approach\nFirst for each pile, build a prefix sum (aka cummulative sum) up to k elements (we can just trim/ignore if there
# Intuition\nUse DP and prefix sum\n\n# Approach\nFirst for each pile, build a prefix sum (aka cummulative sum) up to k elements (we can just trim/ignore if there is more).\n\nThen focus on the first pile.\nWe can take first coin, or two, or ... k and then deal with smaller problem (one less pile and same or less coins to consider).\n\nSo the base cases are:\n- we have considered all piles\n- we have no more coins to take\n\nIn the meoized helper DP function, we take two parameters:\n`start_pile` - index of the pile we focus on (and later deal only with piles with bigger index)\n`hp` - the helper version of k, that is remaining coins we need to consider\n\nOn the helper function we looking for the maximum,\nconsidering taking from the start_pile 0 up to hk coins and remaining coins from the next piles recursively.\n\nHaving such helper function, the answer will be found by `helper(start_pile=0, hk=k)`\n\nIf you find it helpful please up-vote. Thank you!\n\n# Complexity\n- Time complexity: $$O(n\\times k)$$ I think...\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n\\times k)$$ I think...\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n        n = len(piles)\n\n        # Turn each pile to cummulative sum trimmed to k elements\n        for pi in range(n):\n            piles[pi] = list(accumulate(piles[pi][:k]))\n        \n        @cache\n        def helper(start_pile: int, hk: int):\n            if start_pile >= n or hk == 0:\n                return 0\n            # Consider we don\'t take anything from start_pile\n            ans = helper(start_pile + 1, hk)\n            for i, v in enumerate(piles[start_pile], start=1):\n                # Consider we take first i coins from start_pile\n                ans = max(ans, v + helper(start_pile + 1, hk - i))\n                if i == hk:\n                    break\n            return ans\n        \n        return helper(0, k)```
['Dynamic Programming', 'Prefix Sum', 'Python3']