代码随想录算法训练营第四十三天|1049. 最后一块石头的重量 II、494. 目标和、474.一和零

2023-12-24 18:00:28

代码随想录 (programmercarl.com)

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

核心思路:将石头分成重量近似的两堆,与之前的416.分割等和子集问题很相似。

1.确定dp数组以及下标的含义

dp[j]表示容量为j的背包,最多可以背的最大重量为dp[j]。

其中,数组中的数字大小,既是石头的重量,也是石头的价值。

2.确定递推公式

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

本题则是:dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

3.dp数组如何初始化

dp[0] = 0;

题干提示中给出1 <= stones.length <= 30,1 <= stones[i] <= 1000,所以背包最大重量为30 * 1000 。

我们要求的target = 最大重量sum / 2,所以dp数组开到15000大小就可以了,?即dp[1501] = 0。

初始化不需要写0,因为Java默认数组初始化为0。

4.确定遍历顺序

第一层for循环遍历每个石头的重量(价值),第二层for循环遍历背包,从大往小倒序遍历==》确保每个石头只放一次。

5.举例推导dp数组

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for (int i = 0; i < stones.length; i++) {
            for (int j = target; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] - dp[target];
    }
}

494. 目标和

sum表示集合总和,target是目标值,left表示正数+集合,right表示负数-集合。

left + right = sum

left - right = target ==> left - (sum - left) = target ==> left = (target + sum) / 2

所以问题变为,给定一个背包,容量为left,问有多少种方式能够把这个背包装满。

1.确定dp数组以及下标的含义

dp[j]表示装满背包容量为j的背包,有dp[j]种方法

2.确定递推公式

例如:dp[j],j 为5,

  • 已经有一个1(nums[i]) 的话,有 dp[4]种方法 凑成 容量为5的背包
  • 已经有一个2(nums[i]) 的话,有 dp[3]种方法 凑成 容量为5的背包
  • 已经有一个3(nums[i]) 的话,有 dp[2]种方法 凑成 容量为5的背包
  • 已经有一个4(nums[i]) 的话,有 dp[1]种方法 凑成 容量为5的背包
  • 已经有一个5 (nums[i])的话,有 dp[0]种方法 凑成 容量为5的背包

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

3.dp数组如何初始化

dp[0] = 1;代入具体情形进行判断初始化数值

4.确定遍历顺序

0-1背包问题,右边的值由左边确定,每个物品只能放一次,第一层顺序遍历物品,第二层倒序遍历背包。

5.举例推导dp数组

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        //如果target过大 sum将无法满足,题干说明是非负整数数组sum一定>0
        if (sum < Math.abs(target)) {
            return 0;
        }
        //正数集合容量如果不能整除则表明没有解决方案
        if ((target + sum) % 2 != 0) {
            return 0;
        }
        int left = (sum + target) / 2;
        int[] dp = new int[left + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = left; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[left];
    }
}

474.一和零 ?

1.确定dp数组以及下标的含义

三个变量:m,n,最多有多少个物品,需要定义二维数组。

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]);

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

其中,m,n相当于背包的最大容量,每个物品的重量为x个0,y个1,后面+1相当于加上了这个物品的价值,也就是1组包含x个0和y个1的数字。

3.dp数组如何初始化

dp[0][0] = 0; 其他非零下标也初始化为0,便于后续取最大值max。

4.确定遍历顺序

第一层遍历物品(此处为数组中一个一个的字符串),接着遍历字符串的每个字符,统计出字符串中0和1的个数;

注意:每次循环遍历计数之后,需要再次清零,重新遍历。即初始化变量zeroNum = 0;oneNum = 0;需要写在循环里。

第二层倒序遍历背包,背包容量为m个0,n个1,两个维度,两个for循环。

5.举例推导dp数组

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        int zeroNum, oneNum;
        for (String str : strs) {
            zeroNum = 0;
            oneNum = 0;
            for (char ch : str.toCharArray()) {
                if (ch == '0') {
                    zeroNum++;
                } else {
                    oneNum++;
                }
            }
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
}

文章来源:https://blog.csdn.net/YOYU_/article/details/135154830
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。