背包类别
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. 目标和
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.一和零
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).
