#2218

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Value of K Coins From Piles

Optimize coin selection across multiple piles using state transition dynamic programming to achieve the maximum wallet value efficiently.

array dynamic programming prefix sum

Problem Statement

You are given n piles of coins on a table. Each pile contains a positive number of coins in various denominations arranged from top to bottom. On each move, you may pick the top coin from any pile and add it to your wallet.

Given a list piles where piles[i] represents the ith pile and a positive integer k, determine the maximum total value obtainable in your wallet if you pick exactly k coins in the best possible way. Optimize your choice using dynamic programming to consider cumulative coin values per pile.

Examples

Example 1

Input: piles = [[1,100,3],[7,8,9]], k = 2

Output: 101

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

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

Solution Approach

Compute Prefix Sums for Each Pile

Precompute prefix sums for all piles to quickly determine the total value of taking the first j coins from a pile. This enables constant-time lookups during state transitions in the DP solution.

Dynamic Programming State Transition

Define dp[i][j] as the maximum value achievable using the first i piles and selecting j coins. Transition by iterating over the number of coins to take from the current pile and updating dp[i][j] with the maximum sum using dp[i-1][j-x] plus the prefix sum of x coins.

Iterate Efficiently with Constraints

Limit iterations to k coins and handle piles with fewer than k coins carefully. Using prefix sums and the DP table avoids redundant calculations and ensures time complexity remains manageable within constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * k^2) if iterating over all possible coins per pile, but using prefix sums can optimize constant factors. Space complexity is O(n * k) for the DP table, reducible to O(k) with rolling arrays.

What Interviewers Usually Probe

They may ask about handling piles with different lengths in DP transitions.
Expect questions on how prefix sums improve efficiency over brute-force accumulation.
They often test understanding of state definition and iterative DP updates for exact k selections.

Common Pitfalls or Variants

Common pitfalls

Forgetting to consider piles with fewer than the remaining coins in DP updates.
Mixing up top-to-bottom order when computing prefix sums, which breaks correctness.
Not initializing the DP table correctly for zero coins or zero piles cases.

Follow-up variants

Maximize total coins from exactly k piles instead of coins per pile.
Minimize the total coin value for k coins using similar DP structure.
Allow removing multiple top coins in one move and recompute DP accordingly.

FAQ

What is the core strategy for solving Maximum Value of K Coins From Piles?

Use state transition dynamic programming combined with prefix sums to compute the optimal total value when choosing exactly k coins.

How do prefix sums help in this problem?

Prefix sums allow quick computation of the total value of taking the first j coins from a pile, reducing redundant summations during DP transitions.

Can we optimize space in the DP solution?

Yes, a rolling array can reduce space from O(n * k) to O(k) while maintaining correct state transitions.

What happens if a pile has fewer coins than remaining selections?

DP updates should only consider taking up to the available coins in a pile to avoid invalid states.

Is this problem only solvable with dynamic programming?

Yes, because choosing the optimal combination of k coins across multiple piles requires tracking cumulative states, which DP efficiently handles.

terminal

Solution

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.

1

2

3

4

5

6

7

8

9

10

11

12

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]

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.

1

2

3

4

5

6

7

8

9

10

11

12

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]

Continue Practicing

#2100 find good days to rob the bank #2420 find all good indices #2439 minimize maximum of array