代码随想录Day36 | 1049.最后一块石头的重量 II,494.目标和,474.一和零
1049.最后一块石头的重量
视为背包问题，求解 sum / 2 容量背包能装下的最大重量
返回的是 这一部分石头 与 另一部分 的差值的绝对值
代码即为经典的01背包问题
class Solution {
public int lastStoneWeightII(int[] stones) {
if (stones.length == 1) return stones[0];
// 视为背包问题，求解 sum / 2 容量背包能装下的最大重量
// 返回的是 这一部分石头 与 另一部分 的差值的绝对值
int sum = Arrays.stream(stones).sum();
int target = sum / 2;
int[] dp = new int[target + 1];
// dp[i][j]的定义为：
// 从 0-i 取石头，装进容量为 j 的背包可获得的最大重量
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.目标和
与前几道的01背包问题不同，求的是最大价值数，这道题求的是装满背包的种类数（排列组合数）。
在状态转移时仍然是考虑 **取 或 不取数字nums[i] **的两种情况。
可以先写出二维dp的代码，这样便于理解，然后优化为一维dp
class Solution {
public int findTargetSumWays(int[] nums, int target) {
// 题意是将数字分为两部分，它们和的差值是target
// left + right = sum, left - right = target
// left = (sum + target) / 2
// 而且求的是种类数
// 转化为背包问题，求装满 (sum + target) / 2 的种类数
int sum = Arrays.stream(nums).sum();
// 总和都没有 target 绝对值大，无解
if (sum < Math.abs(target)) return 0;
// bag 为小数，无解
if ((sum + target) % 2 != 0) return 0;
int bag = (sum + target) / 2;
// dp[i][j]定义：
// 从 0-i 中取数字，能装满容量为 j 的背包的种类数（排列组合数）
int[][] dp = new int[nums.length][bag + 1];
// 初始化第一行
if (nums[0] <= bag)
dp[0][nums[0]] = 1;
// 初始化第一列，根据 0 的个数取值
// 若是两个0，则每个0取或不取，2的2次
int zeros = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) zeros++;
dp[i][0] = (int) Math.pow(2, zeros);
}
for (int i = 1; i < nums.length; i++) {
for (int j = 1; j <= bag; j++) {
if (nums[i] > j)
dp[i][j] = dp[i - 1][j];
else
// 状态转移：取 或 不取数字nums[i]
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
}
}
return dp[nums.length - 1][bag];
}
}
class Solution {
public int findTargetSumWays(int[] nums, int target) {
// 题意是将数字分为两部分，它们和的差值是target
// left + right = sum, left - right = target
// left = (sum + target) / 2
// 而且求的是种类数
// 转化为背包问题，求装满 (sum + target) / 2 的种类数
int sum = Arrays.stream(nums).sum();
// 总和都没有 target 绝对值大，无解
if (sum < Math.abs(target)) return 0;
// bag 为小数，无解
if ((sum + target) % 2 != 0) return 0;
int bag = (sum + target) / 2;
// dp[i][j]定义：
// 从 0-i 中取数字，能装满容量为 j 的背包的种类数（排列组合数）
// 只用到上一行数据，优化为一维数组，每一行从后往前遍历
int[] dp = new int[bag + 1];
dp[0] = 1;
for (int i = 0; i < nums.length; i++) {
for (int j = bag; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[bag];
}
}
474.一和零
难点在于将问题转换为动态规划问题：
- 视为01背包问题，但是物品的价值有0的个数和1的个数两个维度
- 循环时，遍历物品、背包的0容量、1容量 三个维度
- 按照标准dp就应该是三维dp，优化为二维dp
然后就是背包问题的代码形式
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
// dp[i][j]定义：
// 最多包含 i个0 和 j个1 时，strs的最大子集长度
int[][] dp = new int[m + 1][n + 1];
// 这道题可以视为01背包，但是物品的价值有0和1两个维度
// 循环时，遍历物品、背包的0容量、1容量 三个维度
// dp本来应该是三维，优化到二维，从后往前遍历
for (String str : strs) {
// 统计当前str的 0，1 个数
int ones = 0, zeros = 0;
for (char c : str.toCharArray()) {
if (c == '1') ones++;
else zeros++;
}
for (int i = m; i >= zeros; i--) {
for (int j = n; j >= ones; j--) {
// 状态转移方程：选 或 不选 当前str 两种情况
// 选的话 次数 +1
dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
}
}
}
return dp[m][n];
}
}