2218. Maximum Value of K Coins From Piles

Maximum Value of K Coins From Piles

題目描述： 給定 n 堆硬幣 piles，每堆是一個陣列。每步可以從任一堆的頂端取一枚硬幣。總共取 k 次，求能獲得的最大硬幣總價值。

解題思路： 這是一個分組背包問題：

1. 每堆硬幣是一個「分組」，從第 i 堆取 j 枚硬幣的價值為該堆前 j 枚的前綴和。
2. 用 DP 解決：定義 dp[i][j] = 考慮前 i 堆，總共取 j 枚硬幣的最大價值。
3. 轉移：對於第 i 堆，枚舉從中取 0 到 min(k, piles[i].size()) 枚硬幣。
4. dp[i][j] = max over t in [0, min(j, len_i)] of (dp[i-1][j-t] + prefix_i[t])
5. 答案為 dp[n][k]。

可用一維滾動陣列優化空間。

時間複雜度：O(n * k * m) — n 為堆數，k 為取硬幣總數，m 為每堆平均硬幣數。更精確地說是 O(k * sum(len_i))。

空間複雜度：O(k) — 一維 DP 陣列。

記憶化搜尋 O(n * k * m)：定義 dfs(i, remaining) = 從第 i 堆開始，剩餘 remaining 次取硬幣的最大價值。對每堆枚舉取 0 到 min(remaining, len) 枚。邏輯更直觀但有遞迴開銷。

二維 DP O(n * k * m)：使用 dp[i][j] 二維陣列而非滾動陣列。空間 O(n * k)，更容易理解但空間較大。

1. 如果每堆的硬幣可以從頂端或底端取（雙端隊列），問題如何變化？
2. 此題與經典 0/1 背包問題的關係是什麼？如何用背包框架理解？
3. 如果 k 非常大（接近所有硬幣總數），是否有更快的解法？