leetcode刷题：动态规划09（最后一块石头的重量 II）

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

力扣题目链接

题目难度：中等

有一堆石头，每块石头的重量都是正整数。

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

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

示例：
输入：[2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

提示：

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 1000

dp[j]为 容量为 j 的背包
则每次如果取石头 stones[i] 则dp[j]的剩余容量为Math.max(dp[j],dp[j-stones[i]]+stone[i]),
如果不取这个石头，则不变
/**
* 把石头总重量均分为两堆，最后一相减，就得到最后是否还有剩余石头
* 即：找到容量为一半时可以装入的石头，和剩余石头容量比较，就可以得到所求剩余石头重量
* 1. dp[j]:容量为j的背包可以装下的最大石头数量。j取石头总数的一半，dp[j]<=j
* 因为到时候需要与剩下的石头重量相减
* 2. 确定递推公式 stones是背包已经装的石头数量，dp[j-stones[i]]求背包剩下容量还可以装的石头
* 3.dp数组初始化：dp[j]每次取最大值，所以取0就可以，dp[j]才不会初始值覆盖，石头重量肯定>0
* 4.确定遍历顺序：先遍历石头个数，再重后往前遍历背包（从前往后会导致已经得到的dp[i]被重复使用）
*/

package com.programmercarl.dynamic;

/**
 * @ClassName LastStoneWeightII
 * @Descriotion TODO
 * @Author nitaotao
 * @Date 2022/7/27 15:55
 * @Version 1.0
 * https://leetcode.cn/problems/last-stone-weight-ii/
 * 1049. 最后一块石头的重量 II
 **/
public class LastStoneWeightII {
    public int lastStoneWeightII(int[] stones) {
        /**
         * 把石头总重量均分为两堆，最后一相减，就得到最后是否还有剩余石头
         * 即：找到容量为一半时可以装入的石头，和剩余石头容量比较，就可以得到所求剩余石头重量
         * 1. dp[j]:容量为j的背包可以装下的最大石头数量。j取石头总数的一半，dp[j]<=j
         * 因为到时候需要与剩下的石头重量相减
         * 2. 确定递推公式 stones是背包已经装的石头数量，dp[j-stones[i]]求背包剩下容量还可以装的石头
         * 3.dp数组初始化：dp[j]每次取最大值，所以取0就可以，dp[j]才不会初始值覆盖，石头重量肯定>0
         * 4.确定遍历顺序：先遍历石头个数，再重后往前遍历背包（从前往后会导致已经得到的dp[i]被重复使用）
         */
        //总石头重量和
        int sum = 0;
        for (int i = 0; i < stones.length; i++) {
            sum += stones[i];
        }
        //   / 向下取整    sum/2>=target
        int target = sum / 2;
        //dp[j]:容量为j的背包可以装下的最大石头数量。j取石头总数的一半，dp[j]<=j
        // j 容量   dp[j] 容量为j的背包
        int[] dp = new int[target + 1];
        //先遍历石头
        for (int i = 0; i < stones.length; i++) {
            //从后往前遍历的
            //j 初始值为背包总容量
            for (int j = target; stones[i] <= j; j--) {
                //stones[i]<=j   石头体积<=背包容量
                //                放      当前j-store[i] 容量的背包 装 stones[i]
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        //减去两个相同大小的石堆
        return sum - dp[target] * 2;
    }

    public static void main(String[] args) {
        System.out.println(new LastStoneWeightII().lastStoneWeightII(new int[]{2, 7, 4, 1, 8, 1}));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

代码随想录刷题停更了，xmd，我刷不动了，要去好好听课练练了55555555555