动态规划之练习【9】

 首先 一维数组的 dp 写法，复习的时候再写一遍二维dp。

class Solution {
public:
    int lastStoneWeightII(vector& stones) 
    {
        //化为 0-1 背包问题：
        //现在有 x1 x2 x3..xn y 重量的石头
        //如果 x1+x2+...xn=y 此时返回0
        //如果 1+x1+x2+...+xn=y，此时返回1 为最小重量
        //原因:每次 拿 y 与 xn 相粉碎， 剩下 y-xn 重量，再与下一个 xn-1做差，得到 y-xn-xn-1. 以此内推，最后得到
        //y-xn-xn-1-...x2  与 x1，显然 最后一次粉碎 结果为1
        //所以转换背包问题：尽可能将这堆石头分为等重量的两堆，最后将两堆结果相减就能得到目标结果
        
        //0-1背包问题
        //背包容量 最大为 sum/2；
        //取出来的石头不能重复利用；
        //二维数组dp：i 表示石头重量 ，j表示背包容量 表示重量为i的石头与当前背包容量为j时背包的实际最大重量
        //一位滚动数组dp:j表示背包容量为 j时 背包里实际的最大重量
        
        //递推公式：根据 0-1背包 dp[j]=max(dp[j],dp[j-weight[i]]+value[i];
        //初始化：全部置位0，因为重量不为负
        //当 j时，dp[j]=0;
        //遍历顺序；从前往后
        int sum=0;
        for(int weight:stones)
        sum+=weight;
        vectordp(sum/2+1,0);
        for(int i=0;i=stones[i];j--)//保证物品只取一次
            {
                dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        int weight1=max(dp[sum/2],sum-dp[sum/2]);
        int weight2=min(dp[sum/2],sum-dp[sum/2]);
        return weight1-weight2;
    }
};