✔️✔️Easy Solutions in Java ✔️✔️, Python ✔️, and C++ ✔️🧐Look at once 💻 with Exaplanation
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem can be approached using dynamic programming by breaking it down into subpro
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem can be approached using dynamic programming by breaking it down into subproblems. We can create a 2D array dp[i][j] to store the maximum value of coins for choosing j coins from the first i piles. Then, we can iterate through the array and compute the maximum value of coins for each subproblem by trying all possible choices for the current pile and updating the maximum result.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Create a 2D array dp[i][j] to store the maximum value of coins for choosing j coins from the first i piles.\n2. Fill the first row and column of the array with zeros.\n3. Iterate through the array and compute the maximum value of coins for each subproblem by trying all possible choices for the current pile and updating the maximum result.\n4. If not choosing any coin from the current pile gives a better result, use that instead.\n5. The last element of the array is the maximum value of coins for choosing k coins from all the piles.\n\n  \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n^3), where n is the maximum number of coins in a pile. The outer loop runs n times, the inner loop runs k times, and the innermost loop runs n times in the worst case.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(nk), since we are using a 2D array of size (n+1) x (k+1) to store the results.\n\n![image.png](https://assets.leetcode.com/users/images/b427e686-2e5d-469a-8e7a-db5140022a6b_1677715904.0948765.png)\n\n\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution.\uD83D\uDE0A Keep Learning\nPlease give my solution an upvote! \uD83D\uDC4D\nIt\'s a simple way to show your appreciation and\nkeep me motivated. Thank you! \uD83D\uDE0A\n```\n\n# Code\n```java []\nclass Solution {\n    public int maxValueOfCoins(List<List<Integer>> piles, int k) {\n        // create a 2D array to store the maximum value of coins for choosing j coins from the first i piles\n        int[][] dp = new int[piles.size() + 1][k + 1];\n        // fill the first row of the array with zeros\n        Arrays.fill(dp[0], 0);\n        // fill the first column of the array with zeros\n        for (int i = 1; i <= piles.size(); i++) {\n            dp[i][0] = 0;\n        }\n        // iterate through the array and compute the maximum value of coins for each subproblem\n        for (int i = 1; i <= piles.size(); i++) {\n            for (int j = 1; j <= k; j++) {\n                int cur = 0;\n                // try all possible choices for the current pile and update the maximum result\n                for (int x = 0; x < Math.min(piles.get(i - 1).size(), j); x++) {\n                    cur += piles.get(i - 1).get(x);\n                    dp[i][j] = Math.max(dp[i][j], cur + dp[i - 1][j - x - 1]);\n                }\n                // if not choosing any coin from the current pile gives a better result, use that instead\n                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);\n            }\n        }\n        // the last element of the array is the maximum value of coins for choosing k coins from all the piles\n        return dp[piles.size()][k];\n    }\n}\n```\n```javascript []\n/**\n * @param {number[][]} piles\n * @param {number} k\n * @return {number}\n */\n \nvar maxValueOfCoins = function(piles, k) {\n    // Initialize a 2D array dp with dimensions (n+1) x (k+1) to store the maximum value of coins\n    // for choosing j coins from the first i piles\n    const n = piles.length;\n    const dp = Array(n + 1).fill().map(() => Array(k + 1).fill(0));\n    \n    // Iterate through the rows of dp and compute the maximum value of coins for each subproblem\n    for (let i = 1; i <= n; i++) {\n        // Iterate through the columns of dp and compute the maximum value of coins for each subproblem\n        for (let j = 1; j <= k; j++) {\n            let cur = 0;\n            // Iterate through the first j coins of the ith pile and compute the maximum value of coins\n            // for choosing x coins from the ith pile and (j-x) coins from the first (i-1) piles\n            for (let x = 0; x < Math.min(j, piles[i-1].length); x++) {\n                cur += piles[i-1][x];\n                dp[i][j] = Math.max(dp[i][j], cur + dp[i-1][j-x-1]);\n            }\n            // Take the maximum value of coins for choosing j coins from the first (i-1) piles\n            dp[i][j] = Math.max(dp[i][j], dp[i-1][j]);\n        }\n    }\n    // Return the maximum value of coins for choosing k coins from all the piles\n    return dp[n][k];\n};\n\n```\n```python []\nclass Solution(object):\n    def maxValueOfCoins(self, piles, k):\n        """\n        :type piles: List[List[int]]\n        :type k: int\n        :rtype: int\n        """\n        dp = [[0] * (k + 1) for _ in range(len(piles) + 1)]\n        for i in range(1, len(piles) + 1):\n            for j in range(1, k + 1):\n                cur = 0\n                for x in range(min(len(piles[i - 1]), j)):\n                    cur += piles[i - 1][x]\n                    dp[i][j] = max(dp[i][j], cur + dp[i - 1][j - x - 1])\n                dp[i][j] = max(dp[i][j], dp[i - 1][j])\n        return dp[len(piles)][k]\n```\n```C++ []\nclass Solution {\npublic:\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        int n = piles.size();\n        vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));\n        \n        for (int i = 1; i <= n; i++) {\n            for (int j = 1; j <= k; j++) {\n                int cur = 0;\n                for (int x = 0; x < min(j, (int)piles[i-1].size()); x++) {\n                    cur += piles[i-1][x];\n                    dp[i][j] = max(dp[i][j], cur + dp[i-1][j-x-1]);\n                }\n                dp[i][j] = max(dp[i][j], dp[i-1][j]);\n            }\n        }\n        return dp[n][k];\n    }\n};\n```\n# Please Comment\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution comment below if you like it.\uD83D\uDE0A\n```
['Dynamic Programming', 'Python', 'C++', 'Java', 'JavaScript']