2218. Maximum Value of K Coins From Piles

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 i^th 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] <= 10⁵
1 <= 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\), \(\cdots\), \(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 \leq h \leq 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 \times L)\), and the space complexity is \(O(n \times k)\). Here, \(L\) is the total number of coins, and \(n\) is the number of piles.

Python3JavaC++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]

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];
    }
}

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];
    }
};

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]
}

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];
}

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 \times L)\), and the space complexity is \(O(k)\).