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

LXL's Blog / 2024-09-03 / 原文

https://leetcode.cn/problems/last-stone-weight-ii/description/

思路较为巧妙的dp题,关键点在于如何将问题转化为01背包,有点贪心的思想
主要是划分为两堆尽可能相等的石碓,然后判断能否凑出这个偏小的石碓(若干石头中选,能否选出这个价值)
这里根据f[i]的定义可以有两种做法,1.f[i][j]表示前i个石头中选能否凑出重量为j的选法,类型是布尔
2.f[i][j]表示前i个石头中选,选出重量<=j的选法的最大价值,这里的价值也是重量这个数值

class Solution {
    public int lastStoneWeightII(int[] stones) {
        // 由于要两两相撞,因此需要分成两堆尽可能相等的石碓来相互撞
        // 这样就知道目标target是多少了
        // 如此就转换为01背包问题了,在若干石头中选,选出重量为目标的选法的 最大重量
        // 这里重量是价值和体积
        // f[i][j]表示前i个石头中选能否凑出重量为j的重量,那么答案就是f[n][target]
        // f[i][j] = f[i-1][j] || f[i-1][j-stones[i]]
        // f[0][0] = true; // 凑出重量为0的石头显然可以
        int sum = 0;
        for (int s : stones)sum += s;
        int target = sum / 2;
        boolean[][] f = new boolean[stones.length+10][target + 10];
        f[0][0]=true; // 0不是第一个石头,而是一个石头都不选

        for (int i = 1; i <= stones.length; i++) 
        {
            for (int j = 0; j <= target; j++) 
            {
                // 这里stones下标需要偏移一位,因为f[0][0]没选石头,因此stone[i]表示第i+1块石头
                if(j>=stones[i-1]) 
                    f[i][j] = f[i-1][j] || f[i-1][j-stones[i-1]];
                else f[i][j]=f[i-1][j];
            }
        }
        // 倒序给出重量最大的答案
        for(int i=target;;i--)
            if(f[stones.length][i])return sum-2*i;
    }
}

class Solution {
    public int lastStoneWeightII(int[] stones) {
        // 由于要两两相撞,因此需要分成两堆尽可能相等的石碓来相互撞
        // 这样就知道目标target是多少了
        // 如此就转换为01背包问题了,在若干石头中选,选出重量为目标的选法的 最大重量
        // 这里重量是价值和体积
        int sum = 0;
        for (int s : stones) {
            sum += s;
        }

        int target = sum / 2;
        //初始化，dp[i][j]为可以放0-i物品，背包容量为j的情况下背包中的最大价值
        int[][] dp = new int[stones.length][target + 1];
        //dp[i][0]默认初始化为0
        //dp[0][j]取决于stones[0]
        for (int j = stones[0]; j <= target; j++) {
            dp[0][j] = stones[0];
        }

        for (int i = 1; i < stones.length; i++) {
            for (int j = 0; j <= target; j++) {//注意是等于
                if (j >= stones[i]) {
                    //不放:dp[i - 1][j] 放:dp[i - 1][j - stones[i]] + stones[i]
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return sum - 2*dp[stones.length - 1][target];
    }
}