1049. 最后一塊石頭的重量 II

有一堆石頭，用整數(shù)數(shù)組 stones 表示。其中 stones[i] 表示第 i 塊石頭的重量。

每一回合，從中選出任意兩塊石頭，然后將它們一起粉碎。假設石頭的重量分別為 x 和 y，且 x <= y。那么粉碎的可能結(jié)果如下：

• 如果 x == y，那么兩塊石頭都會被完全粉碎；
• 如果 x != y，那么重量為 x 的石頭將會完全粉碎，而重量為 y 的石頭新重量為 y-x。

最后，**最多只會剩下一塊 **石頭。返回此石頭 **最小的可能重量 **。如果沒有石頭剩下，就返回 0。

示例 1：

**輸入：**stones = [2,7,4,1,8,1]
**輸出：**1
**解釋：**
組合 2 和 4，得到 2，所以數(shù)組轉(zhuǎn)化為 [2,7,1,8,1]，
組合 7 和 8，得到 1，所以數(shù)組轉(zhuǎn)化為 [2,1,1,1]，
組合 2 和 1，得到 1，所以數(shù)組轉(zhuǎn)化為 [1,1,1]，
組合 1 和 1，得到 0，所以數(shù)組轉(zhuǎn)化為 [1]，這就是最優(yōu)值。

示例 2：

**輸入：**stones = [31,26,33,21,40]
**輸出：**5

提示：

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 100

這一題很難想到背包問題

這道題看出是背包問題比較有難度
最后一塊石頭的重量：從一堆石頭中,每次拿兩塊重量分別為x,y的石頭,若x=y,則兩塊石頭均粉碎;若x<y,兩塊石頭變?yōu)橐粔K重量為y-x的石頭求最后剩下石頭的最小重量(若沒有剩下返回0)
問題轉(zhuǎn)化為：把一堆石頭分成兩堆,求兩堆石頭重量差最小值

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int n = stones.size();int sum = 0;for (auto u : stones) {sum += u;}int bag = sum / 2;vector<int> dp(bag + 1, 0);for (int i = 0; i < n; i++) {for (int j = bag; j >= stones[i]; j--) {dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - dp[bag];}
};