1049. Last Stone Weight II

Medium

Description

給定一組石頭重量，每次選兩塊石頭碰撞，重量相同則都消失，否則剩下差值的石頭。回傳最後可能的最小石頭重量。

Example:

Input: stones = [2,7,4,1,8,1] Output: 1

Intuition#

本質是將石頭分成兩組，使兩組重量差最小 — 即 0/1 背包問題。

碰撞過程等價於給每塊石頭分配 + 或 - 號，求最小絕對值
目標是找一個子集，使其和盡量接近 totalSum / 2
轉化為容量為 totalSum / 2 的 0/1 背包問題

Approaches#

1: 2D DP 背包#

概念: dp[i][j] 表示前 i 塊石頭能否湊出重量 j，找到最接近 sum/2 的可達重量。
時間複雜度: O(n * sum)
空間複雜度: O(n * sum)

class Solution {
    fun lastStoneWeightII(stones: IntArray): Int {
        val total = stones.sum()
        val target = total / 2
        val dp = Array(stones.size + 1) { BooleanArray(target + 1) }
        dp[0][0] = true

        for (i in 1..stones.size) {
            for (j in 0..target) {
                dp[i][j] = dp[i - 1][j]
                if (j >= stones[i - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - stones[i - 1]]
                }
            }
        }

        for (j in target downTo 0) {
            if (dp[stones.size][j]) return total - 2 * j
        }
        return total
    }
}

⭐2: 1D DP 背包（空間優化）#

概念: 用一維布林陣列記錄可達的重量，從後往前更新避免重複使用。答案為 total - 2 * maxReachable。
時間複雜度: O(n * sum)
空間複雜度: O(sum)

class Solution {
    fun lastStoneWeightII(stones: IntArray): Int {
        val total = stones.sum()
        val target = total / 2
        val dp = BooleanArray(target + 1)
        dp[0] = true

        for (stone in stones) {
            for (j in target downTo stone) {
                dp[j] = dp[j] || dp[j - stone]
            }
        }

        for (j in target downTo 0) {
            if (dp[j]) return total - 2 * j
        }
        return total
    }
}

🔑 Takeaways#

Pattern: 0/1 背包 — 將「分兩組使差最小」轉化為「子集和最接近 total/2」
關鍵技巧: 石頭碰撞問題的本質是分割問題；逆序遍歷保證每個元素只使用一次