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
- Process piles one at a time;
dp[j]is the maximum value obtainable by takingjcoins from the piles seen so far. - For each pile, build prefix sums
prefix[t]= value of taking the toptcoins. - Taking
tcoins from this pile contributesprefix[t]on top ofdp[j - t]from the earlier piles, sodp[j] = max over t of dp[j-t] + prefix[t]. - 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
tcoins always means the topt, which is what the prefix sums encode. - Reading the partially updated layer: transitions must use the previous layer
dp, notnxt, 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 ktable: 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.