C++ | Easiest Solution | Memoization | Top Down DP | Recursive |
APPROACH\nI have two option\nOption 1: I will not anything from the current ith pile\nOption 2: I wiil take some coins the from current ith pile and rest from o
**APPROACH**\n**I have two option**\n**Option 1: I will not anything from the current ith pile**\n**Option 2: I wiil take some coins the from current ith pile and rest from other piles**\n```\nclass Solution\n{\n    public:\n        int dp[1001][2001];\n    int solver(vector<vector < int>> &arr, int coins, int idx=0)\n    {\n\n       \t// I have no coin and no piles\n        if (idx >= arr.size() || coins == 0) return 0;\n\n        if (dp[idx][coins] != -1) return dp[idx][coins];\n\n        int ans = INT_MIN;\n\n       \t//Option1: I will not take anything from this pile\n        ans = solver(arr, coins, idx + 1);\n\n       \t//options2: I will try to take some coins from here and other coins from some other pile ..so that I can have maximum amount\n\n\t\t//current pile size\n        int sz = arr[idx].size();\n        int sum = 0;\n\t\t\n\t //[Need to iterate till min(coins,sz)because we can take only k coins  at max ]\n        for (int i = 0; i < min(coins, sz); i++)\n        {\n            sum = sum + arr[idx][i];\n\n           \t//trying to take some coins from others also including mine\n            ans = max(ans, sum + solver(arr, coins - (i + 1), idx + 1));\n        }\n\n        return dp[idx][coins] = ans;\n    }\n    int maxValueOfCoins(vector<vector < int>> &piles, int k)\n    {\n        memset(dp, -1, sizeof(dp));\n        return solver(piles, k);\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C']