題目描述:
給定 n 堆硬幣 piles,每堆是一個陣列。每步可以從任一堆的頂端取一枚硬幣。總共取 k 次,求能獲得的最大硬幣總價值。
解題思路: 這是一個分組背包問題:
i 堆取 j 枚硬幣的價值為該堆前 j 枚的前綴和。dp[i][j] = 考慮前 i 堆,總共取 j 枚硬幣的最大價值。i 堆,枚舉從中取 0 到 min(k, piles[i].size()) 枚硬幣。dp[i][j] = max over t in [0, min(j, len_i)] of (dp[i-1][j-t] + prefix_i[t])dp[n][k]。可用一維滾動陣列優化空間。
時間複雜度:O(n * k * m) — n 為堆數,k 為取硬幣總數,m 為每堆平均硬幣數。更精確地說是 O(k * sum(len_i))。
空間複雜度:O(k) — 一維 DP 陣列。
1. Initialize dp[0..k] = 0
2. For each pile i:
a. Compute prefix sums: prefix[t] = sum of first t coins in pile i
b. Create new dp array ndp[0..k] = 0
c. For j from 0 to k:
For t from 0 to min(j, len(pile_i)):
ndp[j] = max(ndp[j], dp[j-t] + prefix[t])
d. dp = ndp
3. Return dp[k]記憶化搜尋 O(n * k * m):定義 dfs(i, remaining) = 從第 i 堆開始,剩餘 remaining 次取硬幣的最大價值。對每堆枚舉取 0 到 min(remaining, len) 枚。邏輯更直觀但有遞迴開銷。
二維 DP O(n * k * m):使用 dp[i][j] 二維陣列而非滾動陣列。空間 O(n * k),更容易理解但空間較大。