Easy C++ solution: recursion to memoization using prefix sum
Intuition\nWe can iterate through piles and decide if we want to take something from the pile or not take it. \nIf we decide to take coins from a particular pil
# Intuition\nWe can iterate through piles and decide if we want to take something from the pile or not take it. \nIf we decide to take coins from a particular pile, then we have the choice of how many coins to take.\n\n# Approach\nLet\'s try to think of a recursive solution. \nWe have two choices, to take coins from a particular pile, or to take nothing. Suppose we start from the last pile, then we have two choices:\n\n**notTake: f(i-1, k)**  // *just move to the next pile*\n**take: (sum of x coins) + f(i-1, k-x)**  // *if we decide to take x coins from pile[i], then we need the sum of all coins from 0 to x, and my k is reduced accordingly, this can be done using a for loop*\n\nInstead of calculating sum of x coins everytime I decide to take coins from the pile, we can make a prefix sum array so we can access the sum by going the xth index in the ith pile, it piles[i][x];\n\n\n# Code\n**Recursion:**\n```\nclass Solution {\npublic:\n    int f(int i, int k, vector<vector<int>>& prefixPiles){\n        // if we reach the end of piles, or k becomes 0 we return 0\n        if(i<0 || k==0) return 0;\n\n        int temp=prefixPiles[i].size();\n        //we can only take coins from a pile n times.\n        int n=min(temp, k);\n\n        //move to the next index and k remains same\n        int notTake=f(i-1, k, prefixPiles);\n\n        int take=0;\n        for(int j=0; j<n; j++){\n            //take coins from pile\n            take=max(take, prefixPiles[i][j]+f(i-1, k-j-1, prefixPiles));\n        }\n        //return max\n        return max(take, notTake);\n    }\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        //making a prefix sum array to aviod adding coins everytime.\n        vector<vector<int>> prefixPiles;\n        for(int i=0; i<piles.size(); i++){\n            vector<int> temp;\n            temp.push_back(piles[i][0]);\n            for(int j=1; j<piles[i].size(); j++){\n                temp.push_back(temp[j-1]+piles[i][j]);\n            }\n            prefixPiles.push_back(temp);\n        }\n        //calling recursion starting from the last pile\n        return f(piles.size()-1, k, prefixPiles);\n    }\n};\n```\n\n**Memoization:**\n```\nclass Solution {\npublic:\n    int f(int i, int k, vector<vector<int>>& prefixPiles, vector<vector<int>>& dp){\n        if(i<0 || k==0) return 0;\n\n        //if value is available for a particular index, use it\n        if(dp[i][k]!=-1) return dp[i][k];\n        int temp=prefixPiles[i].size();\n        int n=min(temp, k);\n        int notTake=f(i-1, k, prefixPiles, dp);\n\n        int take=0;\n        for(int j=0; j<n; j++){\n            take=max(take, prefixPiles[i][j]+f(i-1, k-j-1, prefixPiles, dp));\n        }\n        //store max in dp array\n        return dp[i][k]=max(take, notTake);\n    }\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        //making a prefix sum array to aviod adding coins everytime.\n        vector<vector<int>> prefixPiles;\n        for(int i=0; i<piles.size(); i++){\n            vector<int> temp;\n            temp.push_back(piles[i][0]);\n            for(int j=1; j<piles[i].size(); j++){\n                temp.push_back(temp[j-1]+piles[i][j]);\n            }\n            prefixPiles.push_back(temp);\n        }\n        //declare dp array\n        vector<vector<int>> dp(piles.size()+1, vector<int>(k+1,-1));\n        return f(piles.size()-1, k, prefixPiles, dp);\n    }\n};\n```\n**Please upvote if you understood the solution.**
['Array', 'Dynamic Programming', 'Prefix Sum', 'C++']