給定一組石頭重量，每次選兩塊石頭碰撞，重量相同則都消失，否則剩下差值的石頭。回傳最後可能的最小石頭重量。
Example:
Input: stones = [2,7,4,1,8,1] Output: 1
Intuition
TIP
本質是將石頭分成兩組，使兩組重量差最小 — 即 0/1 背包問題。
- 碰撞過程等價於給每塊石頭分配
+或-號，求最小絕對值 - 目標是找一個子集，使其和盡量接近
totalSum / 2 - 轉化為容量為
totalSum / 2的 0/1 背包問題
Approaches
1. 2D DP Knapsack — O(n * sum) / O(n * sum)
- Idea:
dp[i][j]表示前i塊石頭能否湊出重量j，找到最接近sum/2的可達重量。 - Time:
O(n * sum) - Space:
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 Knapsack (space optimized) — O(n * sum) / O(sum)
- Idea: 用一維布林陣列記錄可達的重量，從後往前更新避免重複使用。答案為
total - 2 * maxReachable。 - Time:
O(n * sum) - Space:
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」
- Key trick: 石頭碰撞問題的本質是分割問題；逆序遍歷保證每個元素只使用一次