动态规划06-最后一块石头的重量

题目描述

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；

如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

思路分析

本题的情况就是不断寻找重量最接近的石头，然后最好能够实现石头的消去。最优的情况就是石头消去以后的重量为零，这样一讲，好像就能够跟划分相等子集结合起来了。将集合分成值相等的两个部分，最终得到的就是0，

1. 定义dp[j]的含义：当背包的容量为j的时候，最大的石头的价值是dp[j]，本题情况下的背包容量就是石头总重量的一半。
2. 确定迭代条件：dp[j] = Max(dp[j-1], dp[j-stone[i]]+stone[i])，翻译一下就是是否选择当前的石头，以及对实时价值的评判。
3. 初始化dp数组：由于初始状态什么都还不知道，所以将dp[]数组全部设置成0。
4. 确定遍历顺序：外层循环遍历物品，采用顺序遍历；内层循环遍历背包，采用倒序遍历。
5. 代入数据验证。

代码展示

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        vector<int> dp(15001, 0);
        int sum = 0;
        for (int i = 0; i < stones.size(); i++) sum += stones[i];
        int target = sum / 2;
        for (int i = 0; i < stones.size(); i++) { // 遍历物品
            for (int j = target; j >= stones[i]; j--) { // 遍历背包
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] - dp[target];
    }
};