Maximum Value of K Coins From Piles

How it works

In the bottom-up approach, each pile only depends on the results from the next pile. We can reduce space by using a single 1D array of size k + 1. Processing coins in reverse order ensures we do not overwrite values we still need for the current pile's computation.

Steps

1. Create a 1D array dp of size k + 1, initialized to 0.
2. For each pile in piles:
   • Iterate coins from k down to 1:
     • For each j from 0 to min(coins, len(pile)) - 1:
       • Accumulate the top j + 1 coins' value.
       • Update dp[coins] with dp[coins - (j + 1)] + curPile if larger.
3. Return dp[k].

Complexity

• Time complexity: O(m * k)
• Space complexity: O(n * k)

Where n is the number of piles, k is the number of coins to choose, and m is the total number of coins among all the piles.

Things to watch for

Off-By-One Errors in Coin Counting

When iterating through coins to take from a pile, it is easy to miscount. Taking j + 1 coins means indices 0 through j, so loops should run from 0 to min(coins, pile.size()) - 1. Mixing up whether j represents the count or the last index causes incorrect state transitions.

Forgetting to Consider Skipping a Pile

The option to take zero coins from a pile (skip it entirely) must be explicitly handled. In the DP transition, initialize the result with dp[i + 1][coins] before iterating over how many coins to take. Missing this case means you cannot skip piles, leading to suboptimal or incorrect answers.

Incorrect DP Iteration Order for Space Optimization

In the space-optimized version, iterating coins from 0 to k instead of from k down to 1 causes you to overwrite values you still need for the current pile. Always iterate in reverse when using a 1D DP array to avoid using updated values prematurely.

Accumulating Pile Sum Incorrectly

When computing the value of taking the top j + 1 coins, you must accumulate the sum incrementally: curPile += pile[j]. Recomputing the sum from scratch each iteration is inefficient, and forgetting to accumulate leads to only counting the single coin at index j rather than all coins from 0 to j.

from typing import List

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        dp = [0] * (k + 1)

        for pile in piles:
            for coins in range(k, 0, -1):
                curPile = 0
                for j in range(min(coins, len(pile))):
                    curPile += pile[j]
                    dp[coins] = max(dp[coins], dp[coins - (j + 1)] + curPile)

        return dp[k]

class Solution {
public:
    int maxValueOfCoins(vector<vector<int>>& piles, int k) {
        vector<int> dp(k + 1, 0);

        for (const auto& pile : piles) {
            for (int coins = k; coins >= 1; coins--) {
                int curPile = 0;
                for (int j = 0; j < min(coins, (int)pile.size()); j++) {
                    curPile += pile[j];
                    dp[coins] = max(dp[coins], dp[coins - (j + 1)] + curPile);
                }
            }
        }

        return dp[k];
    }
};