动态规划01背包之1049 最后一块石头的重量 II（第9道）

题目：

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

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

如果 ，那么两块石头都会被完全粉碎；
如果 ，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例：

 

解法：

本题物品的重量为stones[i]，物品的价值也为stones[i]。

对应着01背包里的物品重量weight[i]和 物品价值value[i]。

动规五部曲：

（1）确定dp数组以及下标的含义

01背包中，dp[j]：容量为j的背包，最多可以装的价值为 dp[j]。

本题中，石头的重量是 stones[i]，石头的价值也是 stones[i] ，可以 “ 最多可以装的价值为 dp[j] ” == “ 最多可以背的重量为dp[j] ”

（2）确定递推公式

01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题则是：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

（3）dp数组如何初始化：vector<int> dp(bagweight+1,0);

（4）确定遍历顺序：先遍历物品，后遍历背包容量

（5）举例推导dp数组

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {//背包容量为所有石头重量/2;//转换成01背包问题：背包容量最多能装多少石头int n=stones.size();int sum=accumulate(stones.begin(),stones.end(),0);int bagweight=sum/2;vector<int> dp(bagweight+1,0);for(int i=0;i<n;i++){for(int j=bagweight;j>=stones[i];j--){dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);}}return sum-2*dp[bagweight];}
};