🔥 [LeetCode The Hard Way] 🔥  DP + Memo Explained
Let dp[i][j] be the maximum total value we can have if we pick j elements starting from piles[i]. The answer is dp[0][k]. First we calculate the value if we pic
Let `dp[i][j]` be the maximum total value we can have if we pick `j` elements starting from `piles[i]`. The answer is `dp[0][k]`. First we calculate the value if we pick any elements in the current pile. Then we try to pick at most `min((int) piles[i].size(), k)` elements and find out the max result.\n\n```cpp\nclass Solution {\npublic:\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        int n = piles.size();\n        vector<vector<int>> dp(n, vector<int>(k + 1, -1));\n        function<int(int,int)> dfs = [&](int i, int k) {\n            // reach the end - return 0\n            if (i == n || k == 0) return 0;\n            // calculated previously - return immediately\n            if (dp[i][k] != -1) return dp[i][k];\n            // do not take \n            int res = dfs(i + 1, k), val = 0;\n            // try to take it one by one \n            // calculate the value we could have\n            for (int j = 0; j < min((int) piles[i].size(), k); j++) {\n                // take this element\n                val += piles[i][j];\n                res = max(res, dfs(i + 1, k - 1 - j) + val);\n            }\n            return dp[i][k] = res;\n        };\n        return dfs(0, k);\n    }\n};\n```\n\n```py\nclass Solution:\n    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n        @lru_cache(None)\n        def dp(i, k):\n            # reach the end - return 0\n            if i == len(piles) or k == 0:\n                return 0\n            res = 0\n            # do not take \n            res += dp(i + 1, k)\n            # try to take it one by one \n            # calculate the value we could have\n            take = 0\n            for j in range(min(k, len(piles[i]))):\n                # take this element\n                take += piles[i][j]\n                res = max(res, dp(i + 1, k - 1 - j) + take)\n            return res\n        return dp(0, k)\n```
['Dynamic Programming', 'Memoization', 'Python', 'C++']