Formatted question description: https://leetcode.ca/all/2218.html
2218. Maximum Value of K Coins From Piles (Hard)
There are n
piles of coins on a table. Each pile consists of a positive number of coins of assorted denominations.
In one move, you can choose any coin on top of any pile, remove it, and add it to your wallet.
Given a list piles
, where piles[i]
is a list of integers denoting the composition of the ith
pile from top to bottom, and a positive integer k
, return the maximum total value of coins you can have in your wallet if you choose exactly k
coins optimally.
Example 1:
Input: piles = [[1,100,3],[7,8,9]], k = 2 Output: 101 Explanation: The above diagram shows the different ways we can choose k coins. The maximum total we can obtain is 101.
Example 2:
Input: piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7 Output: 706 Explanation: The maximum total can be obtained if we choose all coins from the last pile.
Constraints:
n == piles.length
1 <= n <= 1000
1 <= piles[i][j] <= 105
1 <= k <= sum(piles[i].length) <= 2000
Companies:
Google
Related Topics:
Array, Dynamic Programming, Prefix Sum
Similar Questions:
Solution 1. Top-down DP
Let dp[i][j]
be the max value of j
coins using piles i ~ N-1
. The answer is dp[0][k]
.
For 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]
.
dp[i][j] = max( dp[i+1][j-t] + sum(i, t) | 0 <= t <= min(j, A[i].size()) )
where sum(i, t) = A[i][0] + ... + A[i][t-1]
The trivial case is dp[N][j] = 0
, i.e. we can’t get any value from the nonexistent A[N]
.
// OJ: https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/
// Time: O(NM) where `M = sum(A[i].size())`
// Space: O(NK)
class Solution {
public:
int maxValueOfCoins(vector<vector<int>>& A, int k) {
int N = A.size(), m[1001][2001] = {};
memset(m, -1, sizeof(m));
function<int(int, int)> dp =[&](int i, int j) {
if (i == N) return 0;
if (m[i][j] != -1) return m[i][j];
int ans = dp(i + 1, j), sum = 0;
for (int t = 1; t <= j && t <= A[i].size(); ++t) {
sum += A[i][t - 1];
ans = max(ans, dp(i + 1, j - t) + sum);
}
return m[i][j] = ans;
};
return dp(0, k);
}
};
Solution 2. Bottom-up DP
// OJ: https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/
// Time: O(NK)
// Space: O(NK)
class Solution {
public:
int maxValueOfCoins(vector<vector<int>>& A, int k) {
int dp[1001][2001] = {}, N = A.size();
for (int i = 0; i < N; ++i) {
for (int j = 1; j <= k; ++j) {
dp[i + 1][j] = dp[i][j];
for (int t = 1, sum = 0; t <= j && t <= A[i].size(); ++t) {
sum += A[i][t - 1];
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - t] + sum);
}
}
}
return dp[N][k];
}
};
The space complexity can be reduced to O(K)
.
// OJ: https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/
// Time: O(NK)
// Space: O(K)
class Solution {
public:
int maxValueOfCoins(vector<vector<int>>& A, int k) {
int dp[2001] = {}, N = A.size();
for (int i = 0; i < N; ++i) {
for (int j = k; j >= 1; --j) {
for (int t = 1, sum = 0; t <= j && t <= A[i].size(); ++t) {
sum += A[i][t - 1];
dp[j] = max(dp[j], dp[j - t] + sum);
}
}
}
return dp[k];
}
};
Discuss
https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/discuss/1886910