Prefix Sum + DP | C++
\nclass Solution {\n    int dfs(int i, int k, int n, vector<vector<int>> &piles, vector<vector<int>> &dp) {\n        if(!k || i == n) return 0;\n        if(dp[i
```\nclass Solution {\n    int dfs(int i, int k, int n, vector<vector<int>> &piles, vector<vector<int>> &dp) {\n        if(!k || i == n) return 0;\n        if(dp[i][k] != -1) return dp[i][k];\n\n        int ans = 0;\n        for(int j=0; j<min((int)piles[i].size(), k); j++) {\n            int notpick = dfs(i + 1, k, n, piles, dp), pick = 0;\n            if(k - j - 1 >= 0) pick = piles[i][j] + dfs(i + 1, k - j - 1, n, piles, dp);\n            ans = max({ans, pick, notpick});\n        }\n        return dp[i][k] = ans;\n    }\npublic:\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        int n = piles.size();\n        for(auto &p : piles) {\n            for(int i=1; i<p.size(); i++) p[i] += p[i - 1];\n        }\n        vector<vector<int>> dp(n, vector<int>(k + 1, -1));\n        return dfs(0, k, n, piles, dp);\n    }\n};\n\n\n```
['Dynamic Programming', 'Memoization', 'Prefix Sum', 'C++']