Leetcode 1049 最后一块石头的重量II-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode 1049 最后一块石头的重量II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题意理解：

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

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

思路转化：我们可以将题目转换为，将石头分为大小相等差不多的两堆，然后相互去撞击，这样留下来的残余的石头就是可剩余的最小重量。

如何将石头分为大小相等的两堆呢。

target=sum(stones[])/2向上取整

res=sum(stones[])-target 表示剩余的石头重量

此时，再一次将题目转换为0-1背包问题：

target表示背包重量，stones表示物品，stones[i]表示第i块石头的重量和价值。

此时问题转换为将物品装入大小为target的背包，能获得的最大价值maxValue

此时石头被分为：maxValue和sum-maxValue大小的两堆

res=|sum-maxValue-maxValue|此时获得最小剩余大小的石头

解题思路：

        首先理解题意，将其转换为一个背包问题，使用动态规划的思路来求解。

动态规划五部曲：

（1）dp[i][j]或dp[i]的含义

（2）递推公式：

dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+values[i])或

dp[j]=max(dp[j],dp[j-weight[i]]+values[i])

（3）根据题意初始化

（4）遍历求解:先遍历包还是先遍历物品

（5）打印——debug

1.动态规划二维dp数组

dp[i][j]表示下标[0,j]的元素任务，放入大小为j的背包，能获得的最大价值
递推公式：dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+values[i])
初始化第一行，第一列。
遍历：由于二维数组完整保留了两个维度所有信息，所以先遍历背包还是先遍历物品，都是可以的。

public int lastStoneWeightII(int[] stones) {
        int sum=0;
        for(int num:stones)sum+=num;
        int target=(int)Math.ceil(sum/2);
        int[][] dp=new int[stones.length][target+1];
        //初始化
        for(int[] tmp:dp) Arrays.fill(tmp,-1);
        for(int i=0;i<stones.length;i++) dp[i][0]=0;
        for(int j=1;j<=target;j++){
            if(stones[0]>j) dp[0][j]=0;
            else dp[0][j]=stones[0];
        }
        //遍历
        for(int i=1;i<stones.length;i++){
            for(int j=1;j<=target;j++){
                if(stones[i]>j){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i]);
                }
            }
        }
        return Math.abs(sum-dp[stones.length-1][target]*2);
    }

Leetcode 1049 最后一块石头的重量II,刷题训练营,leetcode,算法,数据结构,动态规划

2.一维滚动数组——存储压缩

dp[j]表示装满大小为j的背包所能获得的最大价值。
递推公式：dp[j]=max(dp[j],dp[j-weight[i]]+values[i])
初始化：右边的值总是由最左边的值推导而来，而最坐标的值dp[0]表示背包大小为0所能获得的最大价值，所以有dp[0]=0.将所有元素初始化为0
遍历：由于以为滚动数组是二维dp数组的动态行滚动更新，所以遍历顺序总是先物品后背包。

注意：为了防止用同层修改过的值修改本行其他值，导致物体重复放置，故采用倒序遍历背包。

public int lastStoneWeightII2(int[] stones) {
        int sum=0;
        for(int num:stones)sum+=num;
        int target=(int)Math.ceil(sum/2);
        int[] dp=new int[target+1];
        //初始化
        Arrays.fill(dp,0);
        //遍历
        for(int i=1;i<stones.length;i++){
            for(int j=target;j>=0;j--){
                if(stones[i]>j){
                    dp[j]=dp[j];
                }else{
                    dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
                }
            }
        }
        return Math.abs(sum-dp[target]*2);
    }

Leetcode 1049 最后一块石头的重量II,刷题训练营,leetcode,算法,数据结构,动态规划

3.分析

时间复杂度：O(n*target)

空间复杂度：

二维：O(n*target)

一维：O(target)

n是nums的长度，target是sum(stones)/2的大小文章来源地址https://www.toymoban.com/news/detail-792063.html

到了这里，关于Leetcode 1049 最后一块石头的重量II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！