代码随想录算法训练营第四十三天|1049. 最后一块石头的重量 II、494. 目标和、474.一和零
代码随想录 (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];
}
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!