題目描述

有一堆石頭，每塊石頭的重量都是正整數(shù)。

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

如果 x == y，那么兩塊石頭都會被完全粉碎；
如果 x != y，那么重量為 x 的石頭將會完全粉碎，而重量為 y 的石頭新重量為 y-x。
最后，最多只會剩下一塊石頭。返回此石頭最小的可能重量。如果沒有石頭剩下，就返回 0。
示例：

輸入：[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)值。

題目分析

1. 由于抵消可放回，所以可以將題目轉(zhuǎn)換為分為兩堆石頭，這兩堆石頭重量差額最小。
2. 所以轉(zhuǎn)化為經(jīng)典的01背包，背包的容量為sum/2所獲得的石頭的最大價(jià)值。

C++ 代碼

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