C++ Top-down DP
See my latest update in repo LeetCode\n\n\n## Solution 1. Top-down DP\n\nLet dp[i][j] be the max value of j coins using piles i ~ N-1. The answer is dp[0][k].\n
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n\n## Solution 1. Top-down DP\n\nLet `dp[i][j]` be the max value of `j` coins using piles `i ~ N-1`. The answer is `dp[0][k]`.\n\nFor `dp[i][j]`, we can try using `t` elements from `A[i]` (`0 <= t <= min(j, A[i].size())`), getting `A[i][0] + ... + A[i][t-1]` value plus `dp[i+1][j-t]` value (the max value of `j-t` coins using piles `i+1 ~ N-1`). We try different `t`s and assign the max value to `dp[i][j]`.\n\n```\ndp[i][j] = max( dp[i+1][j-t] + sum(i, t) | 0 <= t <= min(j, A[i].size()) )\n            where sum(i, t) = A[i][0] + ... + A[i][t-1]\n```\n\nTrivial case is `dp[N][j] = 0`, i.e. we can\'t get any value from the nonexistent `A[N]`.\n\n```cpp\n// OJ: https://leetcode.com/contest/weekly-contest-286/problems/maximum-value-of-k-coins-from-piles/\n// Author: github.com/lzl124631x\n// Time: O(NK)\n// Space: O(NK)\nclass Solution {\npublic:\n    int maxValueOfCoins(vector<vector<int>>& A, int k) {\n        int N = A.size(), m[1001][2001] = {};\n        memset(m, -1, sizeof(m));\n        function<int(int, int)> dp =[&](int i, int j) {\n            if (m[i][j] != -1) return m[i][j];\n            if (i == N) return 0;\n            int ans = dp(i + 1, j), sum = 0;\n            for (int t = 1; t <= j && t <= A[i].size(); ++t) {\n                sum += A[i][t - 1];\n                ans = max(ans, dp(i + 1, j - t) + sum);\n            }\n            return m[i][j] = ans;\n        };\n        return dp(0, k);\n    }\n};\n```
[]