【1049. 最后一块石头的重量 II】中等题
思路：要学会将问题转化为01背包问题求解（我还是不会转换，看了卡哥的思路才会）
题意要求的是【粉碎后最小的可能重量】，想象一下，如果尽可能地将这堆石头分成重量最接近的两堆石头，即达到两边重量最可能平衡的状态，那么这个重量的差值就是题意要求解的最小可能重量。需要两堆石头重量最接近，相当于求容量为sum/2的书包能产生的最大价值，此时对应两堆石头最可能平衡时的重量差。
例子1：输入：stones = [2,7,4,1,8,1] 输出：1
sum = 23，target = 23 / 2 = 11，不可能将这堆石头恰好分成重量相同的两堆，但是最理想的情况下，是容量为11的背包恰好能装满，那么背包里的石头的重量就是11，剩下的没被装入书包的石头的重量就是23-11=12，那么两堆石头的重量差值就是12-11=1，即和为奇数的数组的最小差值至少为1。
例子2：输入：stones = [1,2,2,1] 输出：0
sum = 6，target = 6 / 2 = 3，有可能将这堆石头分为重量相等的两堆，最理想的情况下，是容量为3的书包恰好能装满，那么背包里的石头的重量就是3，剩下没装入书包的石头重量也是3，则重量的差值就是0，即和为偶数的数组的最小差值至少为0。
例子3：输入：stones = [31,26,33,21,40] 输出：5
sum=151，target = 151 / 2 = 75，容量为75的书包最多能装重量为73的石头，那么剩下的石头的重量为151 - 73 = 78，那么最小差值就是 78 - 72 = 5。
步骤：
1、计算总和
2、计算目标容量
3、初始化数组
4、进行递推：在容量足够的情况下，能考虑放/不放
剪枝(可不写)：如果容量为target书包早就满了，直接返回差值即可
5、返回最小差值
class Solution {
public int lastStoneWeightII(int[] stones) {
// 1、计算总和
int sum = 0;
for(int stone : stones) sum += stone;
// 2、计算目标容量
int target = sum / 2;
// 3、初始化数组
int[] dp = new int[target+1];
// 4、进行递推
for (int i = 0; i < stones.length; i++){
for (int j = target; j >= stones[i]; j--){ // 容量必须倒序遍历，j >= stones[i]确保足够容量放下i
dp[j] = Math.max(dp[j], dp[j-stones[i]] + stones[i]); // 在容量足够的情况下，能考虑放/不放
}
// 剪枝(可不写)：如果容量为target书包早就满了，直接返回差值即可
if (dp[target] == target) return sum % 2 == 0? 0 : 1; //不能直接返回0，如果sum是奇数，差值为1
}
// dp[target]是最平衡的情况下其中一边的重量，另一边的重量是sum - dp[target]，返回最小差值
return (sum - dp[target]) - dp[target];
}
}- 时间复杂度：O(M×N)
- 空间复杂度：O(N)
【494. 目标和】中等题（用数学推导，得多刷几次）
思路：将问题转化为01背包问题求解
根据题意，要为数组中的每个元素加上符号，求使表达式的值为target的方案数。
如果将数组的元素按符号进行分类，即将一部分看作正数分到数组pos中，剩下的看作负数分到数组neg中，出现 posSum - negSum = target 时这个方案成立。
理想情况下，
posSum + negSum = sum (1)
posSum - negSum = target (2)
将(1)+(2)得，posSum = (sum + target) / 2
即如果数组中存在多个元素的和(posSum)等于(sum+target) / 2的情况，则统计共有多少种这样的情况，即得到题目要求的方案数。那么，现在的问题就转换为，求恰好能将容量为(sum+target) / 2的书包装满的方案数 / 元素组合数。
易错点：不能直接将dp[j]定义为容量为 j 的书包产生的最大价值，因为像下面代码那样，只在恰好将容量为posNum装满时次数加1，会忽略前面未装满情况下的组合情况，导致次数少于正确的结果次数。因此，dp[j]应该定义为【恰好装满】容量为 j 的书包的【方案数】。
for (int i = 0; i < nums.length; i++){ for (int j = posSum; j >= nums[i]; j--){ int pre = dp[j]; dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]); if (j == posSum && dp[posSum] == posSum){ // 如果出现posSum容量的书包已满，判断是否是新的方案，是则+1 if (pre <= dp[j - nums[i]] + nums[i]) cnt++; } } }
优化：
1、如果 target > sum，则不可能实现，方案数为0
2、如果 sum + target 为奇数，则不可能实现，方案数为0，因为需要容量恰好为 (sum + target) % 2 为奇数时，sum + target 除以2的真实值为小数，多个整数元素之和不可能为小数，例如sum + target = 7， (sum + target) * 1.0/ 2 = 3.5，需要元素之和为3.5才能使最后的表达式的值为target，但数组中的元素都是整数，不可能实现，因此方案数一定会为0。
3、如果posSum为负数，而元素之和不可能为负数，则方案数一定为0。
难点：
dp[j]代表的是恰好把容量为 j 的书包装满的方案数，而不是最大价值，如何确定递推关系？
方案：
对于0~ i 的元素，恰好装满容量为 j 的书包的方案数 = 没有nums[i]时恰好装满容量为 j 的书包的方案数（dp[j]） + 有nums[i]时恰好装满容量为 j - numms[i] 的书包的方案数（dp[j-nums[i]]）。
重点：理解为什么一定包含第 i 个物品且恰好装满的方案数为dp[j - nums[i]]？
因为肯定包含第 i 个物品，所以需要为第 i 个物品腾出 nums[i] 大小的空间，则背包的容量就变成 j - nums[i]，问题转换为将容量为 j - nums[i] 的书包恰好装满的方案数，即 dp[j - nums[i]]。
注意：
dp[0]应该初始化为1，即恰好装满容量为0的书包的方案数为1，即不装，否则后面计算的所有数值都是0。
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) sum += num;
if (target > sum) return 0;
if ((sum + target) % 2 != 0) return 0;
int posSum = (sum + target) / 2;
if (posSum < 0) return 0; // 元素值都>=0，求和不可能为负数，如果目标和为负数，直接返回0即可
int dp[] = new int[posSum + 1];
int cnt = 0;
dp[0] = 1; // j = 0，书包容量为0，不放或者如果第一个元素刚好是0，则只有放这个方案
for (int i = 0; i < nums.length; i++){
for (int j = posSum; j >= nums[i]; j--){
// 没有nums[i]时和为j的方案数（dp[j]） + 有nums[i]时和为j-numms[i]的方案数（dp[j-nums[i]]）
dp[j] += dp[j-nums[i]];
}
}
return dp[posSum];
}
}- 时间复杂度：O(M×N)
- 空间复杂度：O(N)
【474.一和零】中等题
思路：
1、确定dp[i][j]的含义：
容量有两个维度，m和n,m是0的个数，n是1的个数，dp[i][j]表示最多有m个0和n个1的最大子集长度
2、确定递推关系：
不加第i个元素的最大子集长度 vs 加上第i个元素的最大子集长度，取长的作为答案。
3、确定初始值：
没有遍历字符串前，最大子集长度都是0即可
（难点：只是将一维滚动数组变成了二维滚动数组）
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
// dp[i][j] -> 表示最多有m个0和n个1的最大子集长度
int dp[][] = new int[m+1][n+1]; // 容量有两个维度，m和n,m是0的个数，n是1的个数
for (String str : strs){
// 计算当前字符串的0和1个数
int cnt0 = 0;
for (char c : str.toCharArray()){
if (c == '0') cnt0++;
}
int cnt1 = str.length() - cnt0; // 不是0就是1，总长度-0的个数 = 1的个数
// 滚动更新二维数组
for (int i = m; i >= cnt0; i--){
for (int j = n; j >= cnt1; j--){
// 不加第i个元素的最大子集长度 vs 加上第i个元素的最大子集长度，取长的作为答案
dp[i][j] = Math.max(dp[i][j], dp[i - cnt0][j - cnt1] + 1);
}
}
}
return dp[m][n];
}
}- 时间复杂度：O(K×M×N)，K指数组的长度
- 空间复杂度：O(M×N)
