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:
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.length1 <= n <= 10001 <= piles[i][j] <= 1051 <= k <= sum(piles[i].length) <= 2000
Solutions
Solution 1: Dynamic Programming (Grouped Knapsack)
We define f[i][j] as the maximum value sum of taking j coins from the first i piles. The answer is f[n][k], where n is the number of piles.
For the i-th pile, we can choose to take the first 0, 1, 2, …, k coins. We can use a prefix sum array s to quickly calculate the value sum of taking the first h coins.
The state transition equation is:
f[i][j] = max(f[i][j], f[i - 1][j - h] + s[h])
where 0 ≤ h ≤ j, and s[h] represents the value sum of taking the first h coins from the i-th pile.
The time complexity is O(k × L), and the space complexity is O(n × k). Here, L is the total number of coins, and n is the number of piles.
PythonJavaC++GoTypeScript
class Solution:
def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
n = len(piles)
f = [[0] * (k + 1) for _ in range(n + 1)]
for i, nums in enumerate(piles, 1):
s = list(accumulate(nums, initial=0))
for j in range(k + 1):
for h, w in enumerate(s):
if j < h:
break
f[i][j] = max(f[i][j], f[i - 1][j - h] + w)
return f[n][k](code-box)
class Solution {
public int maxValueOfCoins(List<List<Integer>> piles, int k) {
int n = piles.size();
int[][] f = new int[n + 1][k + 1];
for (int i = 1; i <= n; i++) {
List<Integer> nums = piles.get(i - 1);
int[] s = new int[nums.size() + 1];
s[0] = 0;
for (int j = 1; j <= nums.size(); j++) {
s[j] = s[j - 1] + nums.get(j - 1);
}
for (int j = 0; j <= k; j++) {
for (int h = 0; h < s.length && h <= j; h++) {
f[i][j] = Math.max(f[i][j], f[i - 1][j - h] + s[h]);
}
}
}
return f[n][k];
}
}(code-box)
class Solution {
public:
int maxValueOfCoins(vector<vector<int>>& piles, int k) {
int n = piles.size();
vector<vector<int>> f(n + 1, vector<int>(k + 1));
for (int i = 1; i <= n; i++) {
vector<int> nums = piles[i - 1];
vector<int> s(nums.size() + 1);
for (int j = 1; j <= nums.size(); j++) {
s[j] = s[j - 1] + nums[j - 1];
}
for (int j = 0; j <= k; j++) {
for (int h = 0; h < s.size() && h <= j; h++) {
f[i][j] = max(f[i][j], f[i - 1][j - h] + s[h]);
}
}
}
return f[n][k];
}
};(code-box)
func maxValueOfCoins(piles [][]int, k int) int {
n := len(piles)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, k+1)
}
for i := 1; i <= n; i++ {
nums := piles[i-1]
s := make([]int, len(nums)+1)
for j := 1; j <= len(nums); j++ {
s[j] = s[j-1] + nums[j-1]
}
for j := 0; j <= k; j++ {
for h, w := range s {
if j < h {
break
}
f[i][j] = max(f[i][j], f[i-1][j-h]+w)
}
}
}
return f[n][k]
}(code-box)
function maxValueOfCoins(piles: number[][], k: number): number {
const n = piles.length;
const f: number[][] = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));
for (let i = 1; i <= n; i++) {
const nums = piles[i - 1];
const s = Array(nums.length + 1).fill(0);
for (let j = 1; j <= nums.length; j++) {
s[j] = s[j - 1] + nums[j - 1];
}
for (let j = 0; j <= k; j++) {
for (let h = 0; h < s.length && h <= j; h++) {
f[i][j] = Math.max(f[i][j], f[i - 1][j - h] + s[h]);
}
}
}
return f[n][k];
}(code-box)
Solution 2: Dynamic Programming (Space Optimization)
We can observe that for the i-th pile, we only need to use f[i - 1][j] and f[i][j - h], so we can optimize the two-dimensional array to a one-dimensional array.
The time complexity is O(k × L), and the space complexity is O(k).
PythonJavaC++GoTypeScript
class Solution:
def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
f = [0] * (k + 1)
for nums in piles:
s = list(accumulate(nums, initial=0))
for j in range(k, -1, -1):
for h, w in enumerate(s):
if j < h:
break
f[j] = max(f[j], f[j - h] + w)
return f[k](code-box)
class Solution {
public int maxValueOfCoins(List<List<Integer>> piles, int k) {
int[] f = new int[k + 1];
for (var nums : piles) {
int[] s = new int[nums.size() + 1];
for (int j = 1; j <= nums.size(); ++j) {
s[j] = s[j - 1] + nums.get(j - 1);
}
for (int j = k; j >= 0; --j) {
for (int h = 0; h < s.length && h <= j; ++h) {
f[j] = Math.max(f[j], f[j - h] + s[h]);
}
}
}
return f[k];
}
}(code-box)
class Solution {
public:
int maxValueOfCoins(vector<vector<int>>& piles, int k) {
vector<int> f(k + 1);
for (auto& nums : piles) {
vector<int> s(nums.size() + 1);
for (int j = 1; j <= nums.size(); ++j) {
s[j] = s[j - 1] + nums[j - 1];
}
for (int j = k; j >= 0; --j) {
for (int h = 0; h < s.size() && h <= j; ++h) {
f[j] = max(f[j], f[j - h] + s[h]);
}
}
}
return f[k];
}
};(code-box)
func maxValueOfCoins(piles [][]int, k int) int {
f := make([]int, k+1)
for _, nums := range piles {
s := make([]int, len(nums)+1)
for j := 1; j <= len(nums); j++ {
s[j] = s[j-1] + nums[j-1]
}
for j := k; j >= 0; j-- {
for h := 0; h < len(s) && h <= j; h++ {
f[j] = max(f[j], f[j-h]+s[h])
}
}
}
return f[k]
}(code-box)
function maxValueOfCoins(piles: number[][], k: number): number {
const f: number[] = Array(k + 1).fill(0);
for (const nums of piles) {
const s: number[] = Array(nums.length + 1).fill(0);
for (let j = 1; j <= nums.length; j++) {
s[j] = s[j - 1] + nums[j - 1];
}
for (let j = k; j >= 0; j--) {
for (let h = 0; h < s.length && h <= j; h++) {
f[j] = Math.max(f[j], f[j - h] + s[h]);
}
}
}
return f[k];
}(code-box)
