• 代码随想录刷题|LeetCode 1049. 最后一块石头的重量II 494. 目标和 474.一和零

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

    题目链接：力扣

    思路

            这道题目是让数组中的石头两两相撞，如果重量相同，就可以消除掉， 如果数量不同，就剩下是大重量-小重量

            如果一直看的是将其中的每两个石头拿出来相撞，就陷进去了。
            从大局看，我们可以将这些石头分成两份，如果这两份重量相同，那最终是可以全部消掉的；如果这两份重量不相同，那最终就是大重量-小重量

            那怎么才能将石头分成两份呢，这就跟 416. 分割等和子集 比较相似了

            准备一个容量为 sum / 2 的背包，尽可能装石头，一份就是dp[sum/2]；另一份就是 sum - dp[sum/2]。因为sum/2 是向下取整的，所以 sum - dp[sum/2]  >= dp[sum/2]，那么 sum - dp[sum/2] -  dp[sum/2] 就是我们要求的结果了

            背包问题确实可以变成套路，但是要从题目中怎么抽象出背包问题才是更重要的，也是解决代码的第一步

    最后一块石头的重量||

    1. class Solution {
    2.     public int lastStoneWeightII(int[] stones) {
    3.  
    4.         // 将石头分成两份，先获取背包容量
    5.         int sum = 0;
    6.         for (int stone : stones) {
    7.             sum += stone;
    8.         }
    9.         int target = sum >> 1;
    10.  
    11.         // 创建dp数组
    12.         int[] dp = new int[target + 1];
    13.  
    14.         // 默认就初始化了
    15.  
    16.         // 填充dp数组
    17.         for (int i = 0; i < stones.length; i++) {
    18.             for (int j = target; j >= stones[i]; j--) {
    19.                 dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]);
    20.             }
    21.         }
    22.  
    23.         return sum - dp[target] - dp[target];
    24.     }
    25. }

    494. 目标和

    题目链接：力扣

    思路

    0、求什么 

            真是不看题解毫无思路，看了题解感叹简单，跟416、1049一样，怎么讲问题可以抽象成01背包问题

            背包问题中，物品元素是取或者不取
            这道题目中，元素是加或者减，都是两种情况

            如果是有结果的，那数组中的元素其实被分为两部分，一部分是正数（记做left）；一部分是负数（记做right）
            那么就存在：left + right = sum  =>  right = sum- left   ①
                                 left - right = target  ②
            从①代入②中可以得到 left - (sum - left) = target ,从而得到 left = (sum + target) / 2

            这样其实就转换成了一个01背包问题，数组中如果有一部分数加起来可以达到 (sum + target) / 2，那就说明这个数组中 可以通过”+“”-“表达式得到 target

            (sum + target) / 2 如果除不尽，就说明没有结果

            但是这道题目问的不是是否存在这样的表达式，而是求这样的表达式存在多少种，所以在dp[]数组的定义上有所改变

            这道题属于：装满背包有多少种方法，而不是能不能装满背包的问题

    1、确定dp数组的含义

            dp[] 数组   装满容量为 j 的背包，有dp[j] 种方法

    2、递推公式

            dp[j] 是由 dp[ j - nums[i]] 获得的，这个想起来真的很是抽象

    例如：dp[j]，j 为5，

    • 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 dp[5]。
    • 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 dp[5]。
    • 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 dp[5]
    • 已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 dp[5]
    • 已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 dp[5]

    那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。

            所以求组合类问题的公式，都是类似这种 dp[j] += dp[j - nums[1]]

            这个公式在背包解决排列组合问题的时候还会使用

    3、初始化dp数组

            根基是dp[0],那么dp[0]应该初始化成多少呢？一定要初始化为0

            如果初始化dp[0] = 0,那么整个dp[]数组中的元素都是0，因为后面的元素都是从这个根基得到的

            dp[0] = 1，理论上也很好解释，装满容量为0的背包，有1种方法，就是装0件物品

            dp[j]其他下标对应的数值应该初始化为0，从递归公式也可以看出，dp[j]要保证是0的初始值，才能正确的由dp[j - nums[i]]推导出来

    4、遍历顺序

            nums放在外循环，target在内循环，且内循环倒序

    目标和

    1. class Solution {
    2.     public int findTargetSumWays(int[] nums, int target) {
    3.  
    4.         // 获取数组和
    5.         int sum = 0;
    6.         for (int i : nums) {
    7.             sum += i;
    8.         }
    9.  
    10.         // 没有方案的情况
    11.         if ( (target + sum) % 2 != 0) {
    12.             return 0;
    13.         }
    14.         
    15.         // 获取背包容量
    16.         int bagSize = (target + sum) / 2;
    17.  
    18.         // 如果背包容量小于0.这种情况不可以
    19.         if (bagSize < 0) {
    20.             return 0;
    21.         }
    22.  
    23.         // 创建dp数组
    24.         int[] dp = new int[bagSize + 1];
    25.  
    26.         // 初始化dp数组
    27.         dp[0] = 1;
    28.  
    29.         // 遍历填充dp数组
    30.         for (int i = 0; i < nums.length; i++) {
    31.             for (int j = bagSize; j >= nums[i]; j--) {
    32.                 dp[j] += dp[j - nums[i]];
    33.             }
    34.         }
    35.  
    36.         // 返回结果
    37.         return dp[bagSize];
    38.     }
    39. }

    474.一和零

    题目链接：力扣

    思路

    0、求什么

            本题跟之前不同的是背包有两个维度。m个0， n个1

            数组中的每一元素还是只使用一次，是01背包问题

            本题求的是装满这个背包，最大的物品个数  

    1、确定dp数组的含义

            dp[i][j] 表示 i 个0，j个1，最大背了 dp[i][j] 个物品，最终要求的结果是dp[m][n]

    2、递推公式

            纯01背包的递推公式 dp[j] = max (dp[j] , dp[j - weight[i]] + value[i])

            对于每一个字符串中有  x 个0 ，y 个1

            假设现在要装一个字符串，其中有 x 个0 ，y 个1，那我们需要的上一个状态是 dp[ i - x ][ j - y ]，如果要将当前字符串放进来，那就需要 dp[ i - x ][ j - y ] + 1，如果不放就是dp[ i ][ j ]

    dp[ i ][ j ] = max(dp[ i ][ j ] , dp[ i - x ][ j - y ] + 1);

    3、初始化

            dp[ 0 ][ 0 ] 应该初始化成多少呢，此时背包是0+0 = 0 ，能放进去的物品自然是0，所以dp[0][0]=0

            非0下标应该怎么初始化呢，非0下标下的肯定不能是0，应该是正数，如果初始化一个很大的数，递推公式的时候，递推公式求得值就会被初始化的值覆盖掉，所以应该初始成0，这样才不会覆盖掉结果

    4、遍历顺序

            遍历物品：字符串，取出字符中有几个0 ，几个1
            遍历背包：倒序遍历 

    一和零 

    1. class Solution {
    2.     public int findMaxForm(String[] strs, int m, int n) {
    3.  
    4.         // 创建dp数组
    5.         int[][] dp = new int[m+1][n+1];
    6.  
    7.         // 初始化
    8.         // 默认已经全部初始化为0了
    9.  
    10.         // 填充dp数组
    11.  
    12.         for (String s : strs) {  // 遍历物品：字符串集合
    13.             int zeroNum = 0; // 0的个数
    14.             int oneNum = 0; // 1的个数
    15.             for (char ch : s.toCharArray()) {  // 获取字符串中0和1的个数
    16.                 if (ch == '0') {
    17.                     zeroNum++;
    18.                 } else {
    19.                     oneNum++;
    20.                 }
    21.             }
    22.  
    23.             // 遍历背包
    24.             for (int i = m; i >= zeroNum; i--) {
    25.                 for (int j = n; j >= oneNum; j--) {
    26.                     dp[i][j] = Math.max(dp[i][j],dp[i-zeroNum][j-oneNum] + 1);
    27.                 }
    28.             }
    29.  
    30.         }
    31.  
    32.         return dp[m][n];
    33.     }
    34. }

  • 相关阅读:
    美国访问学者签证有哪些要求？
    Linux提权--第三方软件MYSQL数据库提权(WEB+本地)
    Springboot大学生健康报送系统的设计与实现毕业设计源码091005
    Cyanine5tetrazine（CAS号：1427705-31-4）结构式原理
    【Java】抽象类(abstract)、接口(interface)
    eMMC编程基础 - （一）eMMC相关术语和概念
    武汉星起航：亚马逊卖家如何做好产品的差异化工作？
    Maven 笔记
    QT之QPropertyAnimation动画类的介绍
    在WPF应用程序集中添加新文件时，Page和Window有什么区别
  • 原文地址：https://blog.csdn.net/m0_62575233/article/details/127993879