Maximum Value of K Coins From Piles

hard dp prefix sum knapsack

Problem

There are n piles of coins on a table. Each pile is a list of positive integers; you may take coins only from the top of a pile, in order. Given the piles and a number k, return the maximum total value of coins you can have in your wallet if you take exactly k coins optimally.

Inputpiles = [[1,100,3],[7,8,9]], k = 2

Output101

Take the top two coins of pile 0 (1 then 100) for 101. dp[j] = best value using a budget of j coins across the piles seen so far.

piles (piles separated by ;)

def max_value_of_coins(piles, k):
    dp = [0] * (k + 1)
    for pile in piles:
        prefix = [0]
        for c in pile:
            prefix.append(prefix[-1] + c)
        new = dp[:]
        for j in range(1, k + 1):
            take = 0
            while take < len(prefix) and take <= j:
                cand = dp[j - take] + prefix[take]
                if cand > new[j]:
                    new[j] = cand
                take += 1
        dp = new
    return dp[k]

function maxValueOfCoins(piles, k) {
  let dp = new Array(k + 1).fill(0);
  for (const pile of piles) {
    const prefix = [0];
    for (const c of pile) prefix.push(prefix[prefix.length - 1] + c);
    const next = dp.slice();
    for (let j = 1; j <= k; j++) {
      for (let take = 0; take < prefix.length && take <= j; take++) {
        const cand = dp[j - take] + prefix[take];
        if (cand > next[j]) next[j] = cand;
      }
    }
    dp = next;
  }
  return dp[k];
}

class Solution {
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int[] dp = new int[k + 1];
        for (List<Integer> pile : piles) {
            int[] prefix = new int[pile.size() + 1];
            for (int i = 0; i < pile.size(); i++) prefix[i + 1] = prefix[i] + pile.get(i);
            int[] next = dp.clone();
            for (int j = 1; j <= k; j++) {
                for (int take = 0; take < prefix.length && take <= j; take++) {
                    int cand = dp[j - take] + prefix[take];
                    if (cand > next[j]) next[j] = cand;
                }
            }
            dp = next;
        }
        return dp[k];
    }
}

int maxValueOfCoins(vector<vector<int>>& piles, int k) {
    vector<int> dp(k + 1, 0);
    for (auto& pile : piles) {
        vector<int> prefix(pile.size() + 1, 0);
        for (int i = 0; i < (int)pile.size(); i++) prefix[i + 1] = prefix[i] + pile[i];
        vector<int> next = dp;
        for (int j = 1; j <= k; j++) {
            for (int take = 0; take < (int)prefix.size() && take <= j; take++) {
                int cand = dp[j - take] + prefix[take];
                if (cand > next[j]) next[j] = cand;
            }
        }
        dp = next;
    }
    return dp[k];
}

Explanation

Each pile is a group from which we may take the top 0, 1, 2, … coins — but never skip a coin to reach a deeper one. So a pile offers a small menu of options, and we choose one option per pile while spending a total budget of k coins. That is a classic grouped knapsack.

Because we can only take from the top, taking take coins from a pile always means its first take coins. Their total is a prefix sum, so we precompute prefix[take] for each pile to evaluate any choice in O(1).

dp[j] is the best value achievable using a budget of exactly j coins across the piles processed so far. For each new pile we build next from dp: for every budget j we try every take from this pile, combining dp[j - take] (budget left for earlier piles) with prefix[take].

We copy dp into next first so each pile is used at most once (we read the old table, write the new one). After all piles are folded in, dp[k] is the answer for taking exactly k coins.

Example: piles = [[1,100,3],[7,8,9]], k = 2. Taking the first two coins of pile 0 yields prefix[2] = 101, which beats any split that touches pile 1 (best there is 7 + 8 = 15 or mixing 1 + 7 = 8). So dp[2] = 101.

Time: O(k · total coins) Space: O(k)