有
n堆硬幣，每堆由上往下排列。每次操作只能從某堆的頂部拿一枚硬幣。最多執行k次操作，回傳能拿到的最大硬幣總價值。
Example:
Input: piles = [[1,100,3],[7,8,9]], k = 2 Output: 101 (從第一堆拿 1 和 100)
Intuition
TIP
分組背包問題：每堆硬幣可以取 0 到 min(堆大小, k) 枚，總共取 k 枚，求最大價值。
- 每堆是一個「物品組」，從中選 0~堆大小 個（但只能從頂部連續取）
- 用前綴和計算每堆取前
t枚的總價值 dp[j]表示取j枚硬幣的最大價值
Approaches
1. 2D DP — O(n * k * max_pile_size) / O(n * k)
- Idea:
dp[i][j]表示考慮前i堆、取j枚硬幣的最大價值。對每堆枚舉取t枚。 - Time:
O(n * k * max_pile_size) - Space:
O(n * k)
class Solution {
fun maxValueOfCoins(piles: List<List<Int>>, k: Int): Int {
val n = piles.size
val dp = Array(n + 1) { IntArray(k + 1) }
for (i in 1..n) {
val pile = piles[i - 1]
val prefix = IntArray(pile.size + 1)
for (t in pile.indices) prefix[t + 1] = prefix[t] + pile[t]
for (j in 0..k) {
for (t in 0..minOf(pile.size, j)) {
dp[i][j] = maxOf(dp[i][j], dp[i - 1][j - t] + prefix[t])
}
}
}
return dp[n][k]
}
}⭐ 2. 1D DP (Space Optimized) — O(n * k * max_pile_size) / O(k)
- Idea: 壓縮掉堆的維度，逆序更新保證每堆只選一次。
- Time:
O(n * k * max_pile_size) - Space:
O(k)
class Solution {
fun maxValueOfCoins(piles: List<List<Int>>, k: Int): Int {
val dp = IntArray(k + 1)
for (pile in piles) {
val prefix = IntArray(pile.size + 1)
for (t in pile.indices) prefix[t + 1] = prefix[t] + pile[t]
for (j in k downTo 1) {
for (t in 1..minOf(pile.size, j)) {
dp[j] = maxOf(dp[j], dp[j - t] + prefix[t])
}
}
}
return dp[k]
}
}🔑 Takeaways
- Pattern: 分組背包 — 每堆是一組物品，從每組中選連續前 t 個
- Key trick: 前綴和預處理每堆取前 t 枚的價值；逆序遍歷容量實現空間壓縮