C++ Top-down DP solution with Explaination
Intuition\nTop down dynamic programming.\n\n\nExplanation\ndp[i,k] means picking k elements from pile[i] to pile[n-1].\nWe can pick 0,1,2,3... elements from the
**Intuition**\nTop down dynamic programming.\n\n\n**Explanation**\ndp[i,k] means picking k elements from pile[i] to pile[n-1].\nWe can pick 0,1,2,3... elements from the current pile[i] one by one.\nIt asks for the maximum total value of coins we can have,\nso we need to return max of all the options.\n\n\n**Complexity**\nTime `O(nm)`\nSpace `O(nk)`\nwhere `m = sum(piles[i].length) <= 2000`\n\n***C++ CODE :***\n```\nclass Solution {\npublic:\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        ios::sync_with_stdio(false);\n        cin.tie(NULL);\n        cout.tie(NULL);\n        \n        int n=piles.size();\n        vector<vector<int>> memo(n+1, vector<int>(k+1,0));\n        \n        function <int (int,int)> dp = [&](int i,int k){\n            if(i==n || k==0)\n                return 0;\n            if(memo[i][k]) \n                return memo[i][k];\n            \n            int res=dp(i+1,k), curr=0;\n            \n            for(int j=0;j<piles[i].size() and j<k ;++j){\n                curr += piles[i][j];\n                res=max(res,dp(i+1,k-j-1)+curr);\n            }\n            return memo[i][k]=res;\n        };\n        return dp(0,k);\n    }\n};\n```
['Dynamic Programming']