解題說明
Last Stone Weight II
題目描述：
有一堆石頭，每塊石頭有一個重量。每次選兩塊石頭碰撞，若重量為 x 和 y（x <= y），碰撞後：若 x == y 兩塊都碎；否則剩下 y - x 的碎片。重複直到最多剩一塊石頭。求最後剩餘石頭的最小可能重量。
解題思路： 轉化為 0/1 背包：
核心觀察：碰撞過程等價於將所有石頭分成兩組 A 和 B，最終結果為 |sum(A) - sum(B)|。
證明：每次碰撞相當於對兩塊石頭賦予 + 或 - 號。最終結果是所有石頭帶符號求和的絕對值。
因此問題轉化為：將石頭分成兩組，使兩組重量差最小 → 等價於找最接近 totalSum / 2 的子集和。
這是經典 0/1 背包問題。定義 dp[j] = 是否能從石頭中選出重量和為 j 的子集。找到 dp[j] = true 的最大 j <= totalSum / 2，答案為 totalSum - 2 * j。
C++ 解法
複雜度分析
時間複雜度：O(n * S) — 其中 n 是石頭數量，S 是總重量的一半。
空間複雜度：O(S) — 一維 DP 陣列。
虛擬碼
1. Compute totalSum of all stones.
2. Set target = totalSum / 2.
3. Initialize dp[0..target] = false; dp[0] = true.
4. For each stone s:
For j from target down to s:
dp[j] = dp[j] OR dp[j - s].
5. Find largest j where dp[j] is true.
6. Return totalSum - 2 * j.其他解法
bitset 優化：O(n * S / 64) 時間。用 bitset 替代布林陣列，利用位運算並行處理多個狀態。常數因子大幅降低。
記憶化搜尋：O(n * S) 時間、O(n * S) 空間。遞迴地嘗試每塊石頭選或不選。邏輯更直觀但空間消耗更大。
延伸思考
- 為什麼「碰撞」過程等價於將石頭分成兩組求差值？能否用歸納法嚴格證明？
- 本題與 LeetCode 416（Partition Equal Subset Sum）有何關聯？主要差異是什麼？
- 如果石頭的重量可以是浮點數，DP 方法是否還適用？需要什麼替代方案？