No-brainer DFS solution with cache
Intuition\nIntuition 1: for pile i, I can pick l = 0, 1, ..., min(k, len(pile[i])) coins from pile i;\nIntuition 2: when I pick l coins on pile i, I then can pi
# Intuition\nIntuition 1: for pile i, I can pick l = 0, 1, ..., min(k, len(pile[i])) coins from pile i;\nIntuition 2: when I pick l coins on pile i, I then can pick k-l coins from i+1 to N-1 piles.\n        \n# Approach\nSolve a subproblem: Find the maximum total value if we are picking from ith pile upto (N-1)th pile for a total of k coins.\n\n# Complexity\n- Time complexity:\n$$O(Nmk)$$ - N is the length of piles, m is the number of coins in each pile.\n\n- Space complexity:\n$$O(Nk)$$ - N is the length of piles.\n\n# Code\n```python\nclass Solution:\n    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n        """\n        Intuition 1: for pile i, I can pick l = 0, 1, ..., min(k, len(pile[i])) coins from pile i;\n        Intuition 2: when I pick l coins on pile i, from i+1 to N-1 piles, I then can k-l coins.\n        Subproblem: Find the maximum total value if we pick from i-th pile and up for a total of k coins.\n        """\n        @cache\n        def solve(i: int, k: int) -> int:\n            # end of piles or no more room for any coin\n            if i == len(piles) or k == 0:\n                return 0\n\n            # don\'t pick this pile\n            res = solve(i+1, k)\n            cur_total = 0\n\n            # If we pick this pile, try all possible number of coins that we can pick, e.g. 1, 2, ..., or\n            # up to k or the total number of coins in piles[i] whenever which one comes first.\n            for l in range(min(k, len(piles[i]))):\n                cur_total += piles[i][l]\n\n                # once I pick l+1 coins in i-th pile, then solve the subproblem\n                # for (i+1)th and onward piles, with k-l-1 room left to fill.\n                res = max(res, cur_total + solve(i+1, k-l-1))\n\n            return res\n\n        return solve(0,k)\n```
['Python3']