算法训练Day42|1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零
背包类别
01背包：有n种物品，每种物品只有一个.
完全背包：有n种物品，每种物品有无限个.
多重背包：有n种物品，每种物品个数各不相同.
区别：仅仅体现在物品个数上的不同而已。
确定dp[i][j]数组的含义：[0,i]的物品任取放容量为j的背包里.
LeetCode:1049. 最后一块石头的重量 II
1049. 最后一块石头的重量 II - 力扣（LeetCode）
1.思路
01背包问题，dp[n + 1]初始化大小之所以是 n + 1 ，在于 n 是一个最大容量，且数组下标从 0 开始。
遍历顺序：先遍历物品再遍历背包，后者背包倒序是为了将物品大值先放入背包，保证每个物品只能遍历一次。
递推公式：取决于物品大小和背包容量，如果背包容量 > 物品大小，则允许放入（此时背包状态：dp[j - stones[i]] + stones[i]），否则不允许放入（此时背包状态：dp[j]）,选择两者之中的较大值即可。
2.代码实现
1// 一维似乎更好理解2class Solution {3 public int lastStoneWeightII(int[] stones) {4 int sum = 0;5 for (int num : stones) {6 sum += num;7 }8 int target = sum / 2;9 int[] dp = new int[target + 1];
10 for (int i = 0; i < stones.length; i++) {
11 for (int j = target; j >= stones[i]; j--) {
12 dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
13 }
14 }
15 return sum - 2 * dp[target];
16 }
17}
3.复杂度分析
时间复杂度：O(n^2).
空间复杂度：O(n).
LeetCode: 494. 目标和
494. 目标和 - 力扣（LeetCode）
1.思路
本题可以抽象成01背包问题，中间需要计算一下…
遍历顺序依旧是：先物品再背包，保证物品先放入最大值及元素的唯一性.
分两种情况：sum<0时,取绝对值之后进入遍历.
2.代码实现
1class Solution {2 public int findTargetSumWays(int[] nums, int target) {3 int sum = 0;4 for (int num : nums) {5 sum += num;6 }7 if (target < 0 && sum < -target) return 0;8 if ((target + sum) % 2 != 0) return 0;9 int size = (target + sum) / 2;
10 if (size < 0) size = -size;
11
12 int[] dp = new int[size + 1];
13 dp[0] = 1;
14 for (int i = 0; i < nums.length; i++) {
15 for (int j = size; j >= nums[i]; j--) {
16 dp[j] += dp[j - nums[i]];
17 }
18 }
19 return dp[size];
20 }
21}
3.复杂度分析
时间复杂度：O(n^2).
空间复杂度：O(n).
LeetCode: 474.一和零
474. 一和零 - 力扣（LeetCode）
1.思路
拆解将m和n共同看作背包的整体，字符串中每个元素看成物品。沿用上述遍历顺序和dp[][]数组定义，输出即可.
2.代码实现
1class Solution {2 public int findMaxForm(String[] strs, int m, int n) {3 // dp[i][j] 表示i个0 和 j个1时的最大子集数4 int[][] dp = new int[m + 1][n + 1];5 int one;6 int zero;7 // 先遍历物品8 for (String str : strs) {9 one = 0;
10 zero = 0;
11 // 得出每个字符串元素中包含的0和1的个数
12 for (char ch : str.toCharArray()) {
13 if (ch == '0') {
14 zero++;
15 } else {
16 one++;
17 }
18 }
19 // 倒序遍历背包，保证每个字符串元素只会被用一次
20 for (int i = m; i >= zero; i--) {
21 for (int j = n; j >= one; j--) {
22 dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
23 }
24 }
25 }
26 return dp[m][n];
27 }
28}
3.复杂度分析
时间复杂度：O(kmn). 空间复杂度：O(mn).