【代码训练营】day42 | 1049. 最后一块石头的重量 II 494. 目标和 474.一和零

所用代码 java

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

题目链接：最后一块石头的重量II LeetCode 1049 - 中等

思路

无。

---

把石头分成重量总和近似两堆，然后两堆石头相撞，剩下的就是最小的石头。每个石头只能用一次，01背包！

• dp[j] ： 装满容量为 j 背包，最大重量为dp[j]
• 递推公式：dp[j] = max(dp[j], dp[j-stones[i]] + stones[i])
• 初始化：dp[0] = 0，非零下标 0 背包容量由题意，最多30块石头，每个价值不超过100，所以容量最大3000/2= 1500，即背包的容量可以定义为dp[1501]
• 遍历方向：0<=i<stones.length target<=j<=stone[i]

class Solution {public int lastStoneWeightII(int[] stones) {int sum = 0;for (int stone : stones) {sum += stone;}int target = sum / 2; // 向下取整// leetcode最大3000int[] dp = new int[1501];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]);}}// 由于target是向下取整的，所以// 大的一堆：sum - dp[target] 小的一堆： dp[target]return sum - dp[target] - dp[target];}
}

二维数组：

• dp[i] [j]： 放[0 - i]个石头，在背包容量为j的情况下的最大重量
• 初始化： dp[i] [0]背包为零，重量为零 ， dp[0] [j] 下标为0的石头取决于背包大于等于stones[0]时可以装下

class Solution {public int lastStoneWeightII(int[] stones) {int sum = 0;for (int stone : stones) {sum += stone;}int target = sum / 2; // 向下取整// 初始化int[][] dp = new int[stones.length][target + 1];for (int j = stones[0]; j<= target; j++) {dp[0][j] = stones[0];}// 外层 石头for (int i = 1; i < stones.length; i++) {// 内层 背包for (int j = 1; j <= target; j++) {// 下一块石头装不下，最大重量就是上一块石头的if (j < stones[i]){dp[i][j] = dp[i-1][j];}else {dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-stones[i]] + stones[i]);}}}
//        System.out.println("dp[stones.length-1][target] = " + dp[stones.length-1][target]);return sum - dp[stones.length-1][target] - dp[stones.length-1][target];}
}

总结

同样这题分析，看到这种两两成对的放东西，而且一种物品只能放一个一般都是01背包问题，分析清楚问题才好对症下药。

目标和 LeetCode 494

题目链接：目标和 LeetCode 494 - 中等

思路

无。

---

分成两个集合，一个集合放加法，一个集合放减法：

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

集合里面挑出正数的集合等于(target + sum) / 2，剩下的就是负数的集合， 不能整除，就证明凑不成集合。

所以这题抽象成 背包容量为(target + sum) / 2，判断集合有多少种装满的情况

• dp[j]：装满背包容量为j的背包，有dp[j]种方法
• 递推公式：dp[j] += dp[j-nums[i]]
• 初始化：dp[0] = 1 (空集也是一种方法) 非零下标初始为0
• 遍历顺序：物品：0<=i< nums.length 背包 bagSize=j>=nums[i]

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int num : nums) sum+=num;// 背包（正数）不能是小数或负数if ((target + sum) % 2 == 1 || (target + sum) / 2 < 0) return 0;int bagSize = (target + sum) / 2;// 初始化int[] dp = new int[bagSize+1];dp[0] = 1;// 物品for (int i = 0; i < nums.length; i++) {// 背包for (int j = bagSize; j>= nums[i]; j--){dp[j] += dp[j-nums[i]];
//                System.out.print("dp[j]=" + dp[j] + "\t");}
//            System.out.println();}return dp[bagSize];}
}

二维数组：

• dp[i] [j]：从[0-i]挑选出的放+数字，恰好装满和为j的背包，有dp[i] [j]种

• 递归公式：dp[i] [j] = dp[i-1] [j] + dp[i-1] [j-nums[i]]

  • 上一轮挑选出来的的和，本轮未挑选：dp[i-1] [j]
  • 上一轮加本轮挑选：dp[i-1] [j-nums[i]]

• 初始化：dp[0] [0] = 1 ，dp[i] [0] = 0，

  ​ dp[0] [j] 装nums[0]只有j= nums[0]这一种方法，dp[0] [nums[0]] = 1

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int num : nums) sum+=num;// target的绝对值大于sum，证明背包的数怎么都没法凑成sumif (Math.abs(target) > sum) return 0;if ((target + sum) % 2 == 1) return 0;int bagSize = (target + sum) / 2;// 初始化 - 新开一个物品维度，以防止初始化0的情况int[][] dp = new int[nums.length + 1][bagSize + 1];// 物品维度为0的物品，不一定是0dp[0][0] = 1;// 只放第0个物品，只有背包容量为nums[0]刚好放下if (nums[0] <= bagSize) dp[1][nums[0]] = 1;// 外层 物品for (int i = 1; i < nums.length + 1; i++) {// 内层 背包 // 从0开始遍历是因为我们只初始化了一个点, j=0的情况没有初始化for (int j = 0; j <= bagSize; j++) {if (j < nums[i-1]){// 不会放入背包dp[i][j] = dp[i-1][j];}else {// 可以放入背包 = i-1物品放入背包的数量 +// i-1物品放入背包的数量+再放入nums[i]的物品的最大数量dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];}
//                System.out.print("\tdp[i][j] = " + dp[i][j]);}
//            System.out.println();}return dp[nums.length][bagSize];}
}

总结

背包容量和价值用一个数表示的话，使用一维数组更加方便，只是我们在遍历的时候从后往前遍历行了，以免前面的数据被覆盖。

一和零 LeetCode 474

题目链接：一和零 LeetCode 474 - 中等

思路

无。

---

• dp[i] [j]：装满i个0j个1，最多背dp[i] [j] 个物品
• 递推公式：dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
  • m个0，n个1：dp[i] [j] = max(dp[i] [j], dp[i-x] [j-y] + 1)
  • 加1是物品的价值可看作1，因为每次可以多放一个
• 初始化：dp[0] [0] = 0 ，非0下标也该初始化为0
• 遍历顺序：str=> 统计每个物品有多少个0 1 => 物品重量
  • i=m i>=x 背包容量，这两个顺序可以颠倒
  • j=n j>=y

class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp = new int[m + 1][n + 1];// x表示0的个数，y表示1的个数int x, y;// 遍历每一个物品for (String str : strs) {x = 0;y = 0;// 统计x和y的重量，也就是出现的个数for (char c : str.toCharArray()){if (c == '0') x++;else y++;}// 相当于滚动二维倒叙遍历for (int i = m; i >= x; i--){   // 0的个数for (int j = n; j >= y; j--){   // 1的个数dp[i][j] = Math.max(dp[i][j], dp[i-x][j-y] + 1);}}}return dp[m][n];}
}

总结

本题元素就是物品，每个物品只有一个，所以dp[i-x] [j-y] + 1 这里才是 + 1，就是选了一个物品。