2218. Maximum Value of K Coins from Piles - Explanation

1. Recursion

Intuition

We need to pick exactly k coins from the tops of various piles to maximize total value. For each pile, we can take zero or more coins from the top, but once we move to the next pile, we cannot return. This naturally suggests a recursive approach: at each pile, try all possible numbers of coins to take (from zero up to the pile size or remaining coins), then recurse on the next pile with fewer coins left to pick. The answer is the maximum across all choices.

Algorithm

Define a recursive function dfs(i, coins) that returns the maximum value starting from pile i with coins remaining.
Base case: if i == n, return 0 (no more piles).
First, consider skipping the current pile entirely: res = dfs(i + 1, coins).
Then, for each j from 0 to min(coins, len(piles[i])) - 1:
- Accumulate the sum of the top j + 1 coins from pile i.
- Update res with curPile + dfs(i + 1, coins - (j + 1)).
Return res.
Call dfs(0, k) as the final answer.

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        n = len(piles)

        def dfs(i, coins):
            if i == n:
                return 0

            res = dfs(i + 1, coins)  # skip current pile
            curPile = 0
            for j in range(min(coins, len(piles[i]))):
                curPile += piles[i][j]
                res = max(res, curPile + dfs(i + 1, coins - (j + 1)))
            return res

        return dfs(0, k)

Time & Space Complexity

Time complexity: $O(k ^ n)$
Space complexity: $O(n)$ for the recursion stack.

Where $n$ is the number of piles and $k$ is the number of coins to choose.

2. Dynamic Programming (Top-Down)

Intuition

The plain recursive solution recomputes the same subproblems many times. We can add memoization by storing results for each state (pile index, remaining coins). Once a state is computed, we return the cached result instead of recomputing. This reduces exponential time complexity to polynomial.

Algorithm

Create a 2D array dp of size n x (k + 1), initialized to -1.
Define dfs(i, coins) as before, but before computing, check if dp[i][coins] is already computed. If so, return it.
Compute the result as in the recursive approach.
Store the result in dp[i][coins] before returning.
Call dfs(0, k) as the final answer.

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        n = len(piles)
        dp = [[-1] * (k + 1) for _ in range(n)]

        def dfs(i, coins):
            if i == n:
                return 0
            if dp[i][coins] != -1:
                return dp[i][coins]

            dp[i][coins] = dfs(i + 1, coins)  # skip current pile
            curPile = 0
            for j in range(min(coins, len(piles[i]))):
                curPile += piles[i][j]
                dp[i][coins] = max(dp[i][coins], curPile + dfs(i + 1, coins - (j + 1)))
            return dp[i][coins]

        return dfs(0, k)

Time & Space 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.

3. Dynamic Programming (Bottom-Up)

Intuition

Instead of recursion with memoization, we can fill the DP table iteratively. We process piles from the last to the first. For each pile and each possible number of remaining coins, we compute the best value by considering all options: skip the pile or take some coins from it. The final answer is stored at dp[0][k].

Algorithm

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

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        n = len(piles)
        dp = [[0] * (k + 1) for _ in range(n + 1)]

        for i in range(n - 1, -1, -1):
            for coins in range(k + 1):
                dp[i][coins] = dp[i + 1][coins]

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

        return dp[0][k]

Time & Space 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.

4. Dynamic Programming (Space Optimized)

Intuition

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.

Algorithm

Create a 1D array dp of size k + 1, initialized to 0.
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.
Return dp[k].

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]

Time & Space 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.

Common Pitfalls

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.