DP | Memoization | Easy to understand
In the problem, we have to select *K coins from the given piles of coins. In one step we can select one coin from the top of the n piles.\nOur task is to maximi
In the problem, we have to select ****K**** coins from the given piles of coins. In one step we can select one coin from the top of the n piles.\nOur task is to ****maximize the total money we can get****.\nFrom the ith pile, we can select between 0 to k coins.\nTherefore, for every pile we have choice to take 0 coin to k coins. Simply, we can write the recursive code exploring all the choices.\n\n**Recursive Solution-**\n\n```\nclass Solution {\npublic:\n    int fun(vector<vector<int>>& piles,int ind,int k)\n    {\n        if(k==0 )return 0; // no more coins can be taken\n        if(ind==piles.size())return INT_MIN;// no more piles are left\n        int ans=fun(piles,ind+1,k); // if we take 0 coin from the pile\n        int score=0;\n        int secAns=INT_MIN;\n        for(int i=0;i<k && i<piles[ind].size();i++)// taking 1 to k coins from the pile\n        {\n            score+=piles[ind][i];\n            secAns=max(secAns,score+fun(piles,ind+1,k-i-1));\n        }\n        return max(ans,secAns);                                      \n    }\n    \n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        int n=piles.size();\n        return fun(piles,0,k);\n    }\n};\n```\nAs we can clearly see, we have overlapping subproblems, therefore,  we can solve the problem with the help of Dynamic Programming. \nThe state variables for the given dynamic programming problem are ind(index) and k. \nWe can create a **dp[n][k+1]** and store the answer for the problem with i and k state variables.\n\n**Dynamic Programming (Memoization)-**\n```\nclass Solution {\npublic:\n    int fun(vector<vector<int>>& piles,int ind,int k,vector<vector<int>>&dp)\n    {\n        if(k==0 )return 0;   //no more coins can be taken \n        if(ind==piles.size())return INT_MIN; // no more piles are left\n        if(dp[ind][k]!=-1)return dp[ind][k]; // if already calculated, simply return\n        int ans=fun(piles,ind+1,k,dp); // if we take 0 coin from the pile\n        int score=0;\n        int secAns=INT_MIN;\n        for(int i=0;i<k && i<piles[ind].size();i++) // taking 1 to k coins from the pile\n        {\n            score+=piles[ind][i];\n            secAns=max(secAns,score+fun(piles,ind+1,k-i-1,dp));\n        }\n        return dp[ind][k] = max(ans,secAns);                                      \n    }\n    \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        return fun(piles,0,k,dp);\n    }\n};\n```\nThe above is the memoized dynamic programming solution.
['Dynamic Programming', 'Recursion', 'Memoization', 'C']