Maximum Value of K Coins From Piles — Hard Problem & Solution

There are n piles of coins on a table. piles[i] lists the coins in the i-th pile from top to bottom.

Difficulty: Hard
Topics: Arrays, Dynamic Programming, Prefix Sum
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

There are n piles of coins on a table. piles[i] lists the coins in the i-th pile from top to bottom. In one move you take the coin currently on top of any pile.

Make exactly k moves and return the maximum total value you can collect.

Example 1

Input: piles = [[1,100,3],[7,8,9]], k = 2
Output: 101
Explanation: Take the top two coins of pile 0: 1 + 100.

Example 2

Input: piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7
Output: 706
Explanation: Six 100s plus one 1 — digging down to the 700 would cost six cheap coins.

Example 3

Input: piles = [[1,2,3]], k = 2
Output: 3

Constraints

n == piles.length
1 <= n <= 1000
1 <= piles[i][j] <= 10^5
1 <= k <= sum(piles[i].length) <= 2000

How to solve Maximum Value of K Coins From Piles

Group knapsack over the piles. dp[j] is the best value using exactly j moves among the piles processed so far. Each pile contributes at most one option — take its first t coins for some t — so the transition tries every t against every remaining budget.

Approach

Start with dp[j] = 0 for all j.
For each pile, copy dp into next (the option of taking nothing).
Walk take from 1 to the pile's size, accumulating the prefix sum running.
For each budget j >= take, consider dp[j - take] + running.
Replace dp with next and move to the next pile.

Why it works

The top-only rule is what collapses the choice space: any set of coins taken from one pile must be a prefix of it, so a pile has len + 1 options rather than 2^len subsets. Copying into next before the inner loops is what keeps the groups exclusive — updating dp in place would let a single pile be used twice within one round.

Complexity

Time — O(k · Σ|pile|)
Space — O(k)

Pitfalls

Updating dp in place lets one pile contribute two prefixes.
Exactly k coins must be taken, and the constraints guarantee enough exist.
Coins come off the top, so an expensive coin deep in a pile drags every coin above it along.

Reference solution

Python

from typing import List

def maxValueOfCoins(piles: List[List[int]], k: int) -> int:
    dp = [0] * (k + 1)
    for pile in piles:
        nxt = dp[:]
        running = 0
        for take in range(1, min(len(pile), k) + 1):
            running += pile[take - 1]
            for j in range(take, k + 1):
                nxt[j] = max(nxt[j], dp[j - take] + running)
        dp = nxt
    return dp[k]

JavaScript

var maxValueOfCoins = function(piles, k) {
    var n = piles.length, j;
    var dp = [];
    for (j = 0; j <= k; j++) dp.push(0);
    for (var p = 0; p < n; p++) {
        var next = dp.slice();
        var running = 0;
        for (var take = 1; take <= piles[p].length && take <= k; take++) {
            running += piles[p][take - 1];
            for (j = take; j <= k; j++) {
                var cand = dp[j - take] + running;
                if (cand > next[j]) next[j] = cand;
            }
        }
        dp = next;
    }
    return dp[k];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue