C++ | Recursive DP + Memoization | Prefix Sum | Commented Code
Code\n\nclass Solution {\npublic:\n    const int inf = 1e9;\n    int dp[1001][2001];\n    int help(int idx, int k, vector<vector<int>> &piles)\n    {\n        /
# Code\n```\nclass Solution {\npublic:\n    const int inf = 1e9;\n    int dp[1001][2001];\n    int help(int idx, int k, vector<vector<int>> &piles)\n    {\n        // if no coins left then return 0\n        if (k == 0)\n            return 0;\n\n        // if we have processed all the piles\n        if (idx == piles.size())\n        {\n            // if k is 0 then we have chosen all the coins so return 0\n            if (k == 0)\n                return 0;   \n            // if k is not 0, then this is not valid so return -infinity\n            return -inf;\n        }\n\n        // if we have calculated the state before then return it\n        if (dp[idx][k] != -1)\n            return dp[idx][k];\n            \n        // for the current state initialize answer as 0\n        int ans = -inf;\n\n        // case1: take coins from the current prices {we can choose maximum \'min(k, current pile size)\' coins from the current pile}\n        for (int i = 0; i < min(k, (int)piles[idx].size()); i++)\n            ans = max(ans, piles[idx][i] + help(idx + 1, k - (i + 1), piles));\n\n        // -----------------max(take,nottake)----------------\n        return dp[idx][k] = max(ans, help(idx + 1, k, piles));\n    }\n    int maxValueOfCoins(vector<vector<int>> &piles, int k)\n    {\n        memset(dp, -1, sizeof(dp));\n        int n = piles.size();\n\n        // storing pref in the piles itself\n        for (int i = 0; i < n; i++)\n            for (int j = 1; j < piles[i].size(); j++)\n                piles[i][j] += piles[i][j - 1];\n\n        // answer\n        return help(0, k, piles);\n    }\n};\n```\n\n### Please UPVOTE if you liked.
['Array', 'Dynamic Programming', 'Prefix Sum', 'C++']