Bottom-up DP explained
We define dp[i][j] as the the answer considering 1st i piles for at most j coins. Hence final answer is dp[n][k]. In base case we consider i=0 ie considering ze
We define `dp[i][j]` as the the answer considering 1st `i` piles for at most `j` coins. Hence final answer is `dp[n][k]`. In base case we consider `i=0` ie considering zero piles. This row will be just zeroes. Similarly for `j=0` column also, it will be all zeroes. \n\nConsider any general `dp[i][j]`. \n\nWe can take 0 coins from `i`th pile and all the `j` coins from the first `i-1` piles. The value for this situation is `dp[i-1][j] + 0`.\n\nWe can also take 3 coins from `ith pile` (assume valid) and `j-3` coins from the first `i-1` piles. The value for this situation is `dp[i-1][j-3] + piles[i-1][0]+piles[i-1][1]+piles[i-1][2]`. \n\nSimilarly we can have other possiblities as well. `dp[i][j]` is the maximum of all these possibilities.\n\nWe define `cur` as the number of coins we take from the current pile and `curSum` as the sum of values of these `cur` coins.\n\n\n```\nint maxValueOfCoins(vector<vector<int>>& piles, int k) \n{\n    int n = piles.size();\n    vector<vector<int>> dp(n+1, vector<int>(k+1, 0));\n    for (int i=1; i<=n; i++)\n    {\n        for (int j=0; j<=k; j++)\n        {\n            dp[i][j] = dp[i-1][j]; // cur=0\n            int curSum = 0;\n            for (int cur=1; cur<=min((int)piles[i-1].size(),j); cur++)\n            {\n                curSum += piles[i-1][cur-1];\n                dp[i][j] = max(dp[i][j], dp[i-1][j-cur]+curSum);\n            }\n        }\n    }\n    return dp[n][k];\n}\n```\n\n$$TC= O(n\\sum_{i=1}^n {P_i})$$ where $P_i$ is the size of ith pile.\n$$SC: O(nk)$$
['Dynamic Programming', 'C++']