• 代码随想录刷题|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. int sum = 0;
    5. for (int stone : stones) {
    6. sum += stone;
    7. }
    8. int target = sum >> 1;
    9. // 创建dp数组
    10. int[] dp = new int[target + 1];
    11. // 默认就初始化了
    12. // 填充dp数组
    13. for (int i = 0; i < stones.length; i++) {
    14. for (int j = target; j >= stones[i]; j--) {
    15. dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]);
    16. }
    17. }
    18. return sum - dp[target] - dp[target];
    19. }
    20. }

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

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

  • 相关阅读:
    Linux /proc/iomem与/proc/ioports
    基于Session的认证与授权实践
    FPS游戏之漫谈Shader.globalMaximumLOD
    大模型培训老师叶梓 AI编程的未来:GitHub Copilot的创新之旅与实践智慧
    选择器进阶与表单表格
    前端重绘重排
    数据挖掘技术-绘制折线图
    【前端项目笔记】6 参数管理
    SQL必需掌握的100个重要知识点:使用表别名
    哈佛大学商业评论 --- 第三篇:真实世界中的增强现实
  • 原文地址:https://blog.csdn.net/m0_62575233/article/details/127993879