My Seventieth Page - 最后一块石头的重量Ⅱ - By Nicolas

这篇page是针对leetcode上的1049.最后一块石头的重量Ⅱ所写的。小尼先简单的说明一下这道题的意思，就是有一堆石头，用整数数组stones表示，其中stones[i]表示第i快石头的重量。每一次我们可以从中选出两块石头，然后我们可以将它们一块粉碎，假设石头的重量分别为x和y，且x<=y，下面是给出的两个结果，如果x == y，那么两块石头都会被完全粉碎；如果x!=y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。最后我们只会剩下一块石头，需要返回石头可能重量的最小值，如果没有石头就直接返回0

首先小尼看到这道题是一脸疑惑啊，满脑子都是想着这道题是个什么鬼，这道题怎么完全没思路，这怎么将两个石头选出来的方法都想不出，但是小尼后来才想到这道题其实就是个动态规划的思想。但是首先，我们需要有一个想法，其实虽然说题目要求是每一次选出两块石头去进行粉碎，也就是我们需要不断地选出两块石头，但是我们其实可以就是直接将stones数组直接分成两块大的石头进行碰撞就行了，如果分出来的两块大的石头的重量相等那么直接就是为0，如果不相等，那么直接就是得到它的差值即可。

小尼接下来说明一下这里动态规划的五部曲：

1、确定dp数组以及下标的含义：这里的dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以被dp[j]这么重的石头。

2、确定递推公式：01背包的递推公式是：dp[j] = max(dp[j],dp[j - weight[i]] + value[i])

3、dp数组如何进行初始化：既然dp[j]中的j表示容量，那么最大容量是多少就是所有石头的重量和。

4、确定遍历顺序：因为小尼采用的这一套是一个一维数dp数组，所以我们采用的遍历的顺序就是for循环放在外层，遍历背包的for循环放在内层，且for循环倒序遍历

5、最后我们只需要导出dp数组

小尼接下里拉一下这道题的代码：

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int i : stones){
            sum += i;
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for(int i = 0; i < stones.length; i++){
            for(int j = target; j >= stones[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - 2 * dp[target];
    }
}

小尼也跟大家简单的介绍一下上面的代码，我们既然先要分成两个背包进行碾碎，那么我们又要求出最小值，所以我们就力求两个背包的大小差不多大，所以首先我们直接遍历stones数组，然后将遍历出来的和直接除以二，这就是我们需要放入的我们的背包的大小，然后在这个背包问题中，我们的物品的大小和价格就是对应的stones中对应石头的数据，通过我们的动态规划进行的求解可以得到容量为j的背包放入物品，我们可以得到dp[j]价值最大，其实也就是我们得到的石块的重量最大的时候，最后的return值其实就是一个很有意思的写法，我们通过数学的形式可以想一想，我们得到一个背包中可以放入物品价值的最大值，那么我们另一个背包中可以放入的最大值也是一样的，我们放入将两个背包进行对应的碾压，那么我们直接就是sum-2*dp[target]即可，最后就是碾压完我们两边重叠了的质量，最后就是我们得到的结果。

希望上面的代码和分析可以帮助到小伙伴们~~~