2218. Maximum Value of K Coins from Piles

Hard
Description

有 n 堆硬幣，每堆由上往下排列。每次操作只能從某堆的頂部拿一枚硬幣。最多執行 k 次操作，回傳能拿到的最大硬幣總價值。

Example:

Input: piles = [[1,100,3],[7,8,9]], k = 2 Output: 101 (從第一堆拿 1 和 100)

Intuition#

分組背包問題：每堆硬幣可以取 0 到 min(堆大小, k) 枚，總共取 k 枚，求最大價值。

  • 每堆是一個「物品組」，從中選 0~堆大小 個（但只能從頂部連續取）
  • 用前綴和計算每堆取前 t 枚的總價值
  • dp[j] 表示取 j 枚硬幣的最大價值

Approaches#

1: 2D DP#

  • 概念: dp[i][j] 表示考慮前 i 堆、取 j 枚硬幣的最大價值。對每堆枚舉取 t 枚。
  • 時間複雜度: O(n * k * max_pile_size)
  • 空間複雜度: 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（空間優化）#

  • 概念: 壓縮掉堆的維度，逆序更新保證每堆只選一次。
  • 時間複雜度: O(n * k * max_pile_size)
  • 空間複雜度: 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 個
  • 關鍵技巧: 前綴和預處理每堆取前 t 枚的價值；逆序遍歷容量實現空間壓縮