Cocolib

Appearance

On this page

最后一块石头的重量II ​

TIP

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

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

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

思路 ​

动规五部曲 ​

  1. 确定dp数组以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

如何将问题转化为0-1背包问题，就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了

js
var lastStoneWeightII = function(stones) {
    let sum = stones.reduce((pre,cur)=>pre+cur,0)
    let n = Math.floor(sum/2) //背包容量
    let dp =[]
    for(let j=0;j<=n;j++){
        dp[j] = 0
    }
    for(let i=0;i<stones.length;i++){     //物品
        for(let j=n;j>=stones[i];j--){           //背包
            dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i])
        }
    }
    return sum-2*dp[n]
};