动态规划：12最后一块石头的重量II

动态规划：12最后一块石头的重量II

1049. 最后一块石头的重量 II

分析

要使相撞过后的石头重量最小，我们只需要将石头分为重量相似的两堆就可以了

题目与动态规划：11分割等和子集有异曲同工之妙

五部曲

1. 确定dp数组含义：dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]。

   可以回忆一下01背包中，dp[j]的含义，容量为j的背包，最多可以装的价值为 dp[j]。

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

2. 确定递归公式：dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);

   dp[j] = Math.max(dp[j], (dp[j - weight[i]] + value(i)))

3. dp数组初始化：dp[j] = 0

   重量都不会是负数，所以dp[j]都初始化为0就可以了，这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);中dp[j]才不会初始值所覆盖。

4. 遍历顺序：先物后包，包要倒序

5. debug：打印dp数组

代码

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int i : stones) {
            sum += i;
        }
        int target = sum >> 1;
        //初始化dp数组
        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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 时间复杂度：O(m × n) , m是石头总重量（准确的说是总重量的一半），n为石头块数
• 空间复杂度：O(m)

总结

本题其实和动态规划：11分割等和子集几乎是一样的，只是最后对dp[target]的处理方式不同。

动态规划：11分割等和子集相当于是求背包是否正好装满，而本题是求背包最多能装多少。