Description#
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:
![](https://spcdn.pages.dev/leetcode/problems/2218.Maximum%20Value%20of%20K%20Coins%20From%20Piles/images/e1.png)
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
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
presum = [list(accumulate(p, initial=0)) for p in piles]
n = len(piles)
dp = [[0] * (k + 1) for _ in range(n + 1)]
for i, s in enumerate(presum, 1):
for j in range(k + 1):
for idx, v in enumerate(s):
if j >= idx:
dp[i][j] = max(dp[i][j], dp[i - 1][j - idx] + v)
return dp[-1][-1]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int maxValueOfCoins(List<List<Integer>> piles, int k) {
int n = piles.size();
List<int[]> presum = new ArrayList<>();
for (List<Integer> p : piles) {
int m = p.size();
int[] s = new int[m + 1];
for (int i = 0; i < m; ++i) {
s[i + 1] = s[i] + p.get(i);
}
presum.add(s);
}
int[] dp = new int[k + 1];
for (int[] s : presum) {
for (int j = k; j >= 0; --j) {
for (int idx = 0; idx < s.length; ++idx) {
if (j >= idx) {
dp[j] = Math.max(dp[j], dp[j - idx] + s[idx]);
}
}
}
}
return dp[k];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int maxValueOfCoins(vector<vector<int>>& piles, int k) {
vector<vector<int>> presum;
for (auto& p : piles) {
int m = p.size();
vector<int> s(m + 1);
for (int i = 0; i < m; ++i) s[i + 1] = s[i] + p[i];
presum.push_back(s);
}
vector<int> dp(k + 1);
for (auto& s : presum) {
for (int j = k; ~j; --j) {
for (int idx = 0; idx < s.size(); ++idx) {
if (j >= idx) dp[j] = max(dp[j], dp[j - idx] + s[idx]);
}
}
}
return dp[k];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| func maxValueOfCoins(piles [][]int, k int) int {
var presum [][]int
for _, p := range piles {
m := len(p)
s := make([]int, m+1)
for i, v := range p {
s[i+1] = s[i] + v
}
presum = append(presum, s)
}
dp := make([]int, k+1)
for _, s := range presum {
for j := k; j >= 0; j-- {
for idx, v := range s {
if j >= idx {
dp[j] = max(dp[j], dp[j-idx]+v)
}
}
}
}
return dp[k]
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
| class Solution:
def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
presum = [list(accumulate(p, initial=0)) for p in piles]
dp = [0] * (k + 1)
for s in presum:
for j in range(k, -1, -1):
for idx, v in enumerate(s):
if j >= idx:
dp[j] = max(dp[j], dp[j - idx] + v)
return dp[-1]
|