最后一块石头的重量Ⅱ

题目

实际上就是石头可能存在不能完全打碎的情况，如果能打碎：看那个位置能放多少，

具体思路

1. 遍历数组，找到背包的容量：整个大小的一半；
2. 通过 01背包 问题找到当前容量最多可以放多少；
3. 返回的就是 total - dp[space] * 2

具体实现

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int total = 0;
        for (int i = 0; i < stones.length; i++) {
            total += stones[i];
        }

        int space = total / 2;
        int[] dp = new int[space + 1];
        for (int i = 0; i < stones.length; i++) {
            for (int j = space; j > 0; j--) {
                if (j >= stones[i]) {
                    dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
                }
            }
        }
        return total % 2 == 0 && dp[space] == space ? 0 : total - 2 * dp[space];
    }
}

这里的更新条件是 大于等于

        return total - 2 * dp[space]; 可以直接返回这个，因为如果装满的

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for (int i = 0; i < stones.size(); i++) {
            sum += stones[i];
        }

        int target = sum;
        sum /= 2;

        vector<int> dp(sum + 1, 0);

        for (int i = 0; i < stones.size(); i++) {
            for (int j = sum; j > 0; j--) {
                if (j >= stones[i])
                    dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }

        return target - 2 * dp[sum];
    }
};