[Python] dp solution (complexity updated), explained
Let use dp with states dp(n, k), where it is (current index of pile, nubmer of elements we still need to take). Then on each state we can try to take 0, ..., mi
Let use dp with states `dp(n, k)`, where it is `(current index of pile, nubmer of elements we still need to take)`. Then on each state we can try to take `0, ..., min(k, len(piles[m]))` elements from pile `m`. Also if `n == N`, that is we reached the last pile and `k == 0`, we are happy, return `0`. If `k > 0`, it means that we reached the last pile and did not take `k` elements, we are not happy, return `-inf`.\n\n#### Complexity\nImagine, that piles have `x1, ..., xn` elements in them. Then for state `(1, k)` we have `x1` possible transactions, for state `(2, k)` we have `x2` possible transactions and so on. In total we have `x1 + ... + xn` transactions for every value of `k`. So, in total we have time complexity `O(M * K)`, where `M = x1 + ... + xn`. Space is `O(n * K)`.\n\n#### Code\n```python\nclass Solution:\n    def maxValueOfCoins(self, piles, K):\n        N = len(piles)\n        @lru_cache(None)\n        def dp(n, k):\n            if n == N:\n                if k == 0: return 0\n                if k > 0: return -float("inf")\n            ans = dp(n + 1, k)\n            sm = 0\n            for i in range(min(k, len(piles[n]))):\n                sm += piles[n][i]\n                ans = max(ans, dp(n + 1, k - i - 1) + sm)\n            return ans\n\n        return dp(0, K)\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Dynamic Programming']