DP Solution | Easy to Understand | Step by Step Explanation | C++
Intuition\n \nIt\'s obvious that there is no greedy solution for this problem since there are multiple combinations and also restriction of picking topmost of p
# Intuition\n<!--  -->\nIt\'s obvious that there is no greedy solution for this problem since there are multiple combinations and also restriction of picking topmost of pile.\n So, we are probably going to explore all combinations and choose the most optimal one. \nThis should give a hint for a recursive complete search solution.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nLet the **state** of our DP be DP[i][k].\n\nHere DP[i][k] is defined as the maximum profit we can get starting from the i-th pile and still having room for k more coins.\n\nNow, the **transition** is going to be simple. There are two choices:\n1. Don\'t pick any coin from this pile. In that case, DP[i][k] = DP[i+1][k]\n2. Pick exactly j coins from this pile (given that j <= k).\nIn this case, DP[i][k] = sum of topmost j coins + DP[i+1][k-j].\n\nNow, coming to the **base cases**:\n1. If we don\'t have space for any more coins, then profit will be 0.\n    So, DP[...][0]=0\n2. If we are at the end of our list of piles, we can no longer generate anymore profit. \n    So, DP[n][...]=0\n\nOur final answer, is going to be present in DP[0][k]. \nWe can construct a DP table of size (N*K) and use it to store and fill in the DP values. \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n* k * |pile[i]| )$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n*k)$$\n# Code\nHere\'s the Dynamic Programming Solution:\n```\nclass Solution {\npublic:\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        int n=(int)piles.size();\n        vector<vector<int>>dp;\n        dp.resize(n+1, vector<int>(k+1,0));\n        // State: dp[i][k]-> Max profit starting from i-th pile and remaining k coins\n        // Transition: dp[i][k]=max(dp[i+1][k], (pick first j coins) -> dp[i+1][k-j])\n        // Base Case: dp[n][...]=0, dp[...][0]=0\n        // Final Answer: dp[0][k]\n        for(int i=0;i<n;i++){\n            dp[i][0]=0;\n        }\n        for(int i=n-1;i>=0;i--){\n            for(int coins=0;coins<=k;coins++){\n                // Don\'t take any coin.\n                dp[i][coins]=dp[i+1][coins];\n                int cost=0;\n                // Take j coins (j<=coins)\n                for(int j=0;j<(int)piles[i].size() && j<coins;j++){\n                    cost+=piles[i][j];\n                    dp[i][coins]=max(dp[i][coins], cost + dp[i+1][coins - (j+1)]);\n                }\n            }\n        }\n        return dp[0][k];\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']