Prefix-Sum + Bottom-up dp. DETAILED EXPLANATION. [C++/Python]
\n\n# Code\n\nclass Solution {\npublic:\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        int n = piles.size();\n        // total n piles a
\n\n# Code\n```\nclass Solution {\npublic:\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        int n = piles.size();\n        // total n piles and k coins we can choose.\n        // so for any dp[i][j] it will store the max coins we\n        // get using i piles and j coins used.\n        vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));\n        // Since we want to be dealing with the sums of coins,\n        // it would be real convenient, if our piles just stored\n        // the prefix sum instead. This can be done on the piles\n        // matrix directly, however, it is a good practice to not\n        // to change anything provided in the problem. Make pref\n        vector<vector<int>> pref(n, vector<int>()); // prefix-sum\n        for (int i = 0; i < n; i++) {\n            pref[i].resize(piles[i].size()); // uneven matrix so resize()\n            pref[i][0] = piles[i][0]; // initialize for pref_sum\n            for (int j = 1; j < piles[i].size(); j++) {\n                // calculating prefix sum\n                pref[i][j] = pref[i][j - 1] + piles[i][j];\n            }\n        }\n\n        for (int i = 1; i <= n; i++) {\n            for (int j = 1; j <= k; j++) {\n                // Let the coins chosen from the current pile be cur\n                for (int cur = 0; cur <= piles[i - 1].size(); cur++) {\n                    // Check for all combinations of coins that sum up to j coins.\n                    // We can pick w coins from this pile and j-w coins from previous piles (dp[i-1][j-w]).\n                    // i.e., (j-w) + w = j coins in total.\n                    if(cur <= j)\n                        if(cur > 0){\n                            // if cur > 0 we can consider prefix sum since in-bounds\n                            dp[i][j] = max(dp[i][j], dp[i - 1][j - cur] + pref[i - 1][cur - 1]);\n                        }\n                        else{\n                            dp[i][j] = max(dp[i][j], dp[i - 1][j - cur]);\n                        }\n                }\n            }\n        }\n        return dp[n][k];\n    }\n};\n\n\n```\nPython code for the same:\n```\nclass Solution:\n    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n        n = len(piles)\n        dp = [[0] * (k + 1) for _ in range(n + 1)]\n        pref = [[] for _ in range(n)]  \n        for i in range(n):\n            pref[i] = [0] * len(piles[i])  \n            pref[i][0] = piles[i][0]  \n            for j in range(1, len(piles[i])):\n                pref[i][j] = pref[i][j - 1] + piles[i][j]\n\n        for i in range(1, n + 1):\n            for j in range(1, k + 1):\n                for cur in range(len(piles[i - 1]) + 1):\n                    if cur <= j:\n                        if cur > 0:\n                            dp[i][j] = max(dp[i][j], dp[i - 1][j - cur] + pref[i - 1][cur - 1])\n                        else:\n                            dp[i][j] = max(dp[i][j], dp[i - 1][j - cur])\n        return dp[n][k]\n```
['Prefix Sum', 'Python', 'C++', 'Python3']