⚡Flashcard Drill➔
NeetCode #745LC-2218Hard2-D Dynamic Programming
← Back to All Problems

#745 · #2218 · Maximum Value of K Coins From Piles(从栈中取出 K 个硬币的最大面值和)

📌 Problem Statement & Constraints

There are piles of coins; piles[i][j] is the value of the j-th coin from the top of pile i. You take exactly k coins, and from any pile you may only take a prefix (the top coins). Return the maximum total value. Constraints: 1 <= piles.length <= 1000, 1 <= piles[i].length <= 1000, 1 <= k <= 2000, 1 <= piles[i][j] <= 10^5, and the total number of coins across all piles is at most 2000.

💡 Core Algorithmic Approaches

  1. Process piles one at a time; dp[j] is the maximum value obtainable by taking j coins from the piles seen so far.
  2. For each pile, build prefix sums prefix[t] = value of taking the top t coins.
  3. Taking t coins from this pile contributes prefix[t] on top of dp[j - t] from the earlier piles, so dp[j] = max over t of dp[j-t] + prefix[t].
  4. Each pile is used at most once, so the transition reads the previous layer while writing the next, using a copy to keep the take-zero option.

💻 Benchmark Python3 Implementation

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        dp = [0] * (k + 1)
        for pile in piles:
            # prefix[t] = total value of the top t coins
            prefix = [0]
            for v in pile:
                prefix.append(prefix[-1] + v)
            nxt = dp[:]                # option: take nothing from this pile
            for j in range(1, k + 1):
                best = nxt[j]
                for t in range(1, min(j, len(pile)) + 1):
                    best = max(best, dp[j - t] + prefix[t])
                nxt[j] = best
            dp = nxt
        return dp[k]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(k * total coins): each coin of each pile is considered once per budget state j.
💾 Space Complexity
O(k): two rolling arrays plus per-pile prefix sums.

⚠️ Interview Pitfalls & Follow-ups

  • Taking coins from the bottom of a pile: coins are stacked, so taking t coins always means the top t, which is what the prefix sums encode.
  • Reading the partially updated layer: transitions must use the previous layer dp, not nxt, or the same pile could be consumed twice.
  • Dropping the take-zero option: a pile may contribute nothing, which nxt = dp[:] preserves.
  • Using a 2-D piles x k table: it works but wastes memory; the rolling array is enough.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems