力扣爆刷第73天–动态规划
零、背包问题总纲：
背包问题：一维数组，dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i])。
01背包遍历顺序：先物品后背包，物品正序，背包逆序。
如若背包正序则会出现同一个物品重复放入，如物品1重量为1，背包空间为1时放入了，背包空间为2时又放入了。
如果先背包后物品，为了避免重复放入背包依然是逆序，背包容量固定时，每种背包容量只能放入一个物品，即为最大的物品，小的物品都放不进来或者被覆盖了。
求组合数排列数：dp[j] += dp[j - nums[i]]
完全背包遍历顺序：物品背包没有先后顺序，物品背包都是正序。因为同一个物品不限量可以放入多次，在背包采用正序中。
完全背包求组合数，物品在外，背包在内。求排列数，背包在外，物品在内。
一、416. 分割等和子集
题目链接：https://leetcode.cn/problems/partition-equal-subset-sum/description/
思路：等和分割子集，就是计算出总和的一半，然后把所有元素往里面装看最大值是否能达到一半，能达到即可划分，这就转换成一个背包问题了。
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for(int i = 0; i < nums.length; i++) {
sum += nums[i];
}
if(sum % 2 != 0) return false;
sum = sum / 2;
int[] dp = new int[sum+1];
for(int i = 0; i < nums.length; i++) {
for(int j = sum; j >= nums[i] ; j--) {
dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
}
}
return dp[sum] == sum;
}
}
二、1049. 最后一块石头的重量 II
题目链接：https://leetcode.cn/problems/last-stone-weight-ii/description/
思路：本题说石头之间两两抵消，求最后余数，其实就是把石头划分为两堆，然后计算差值，差值即为最后一块石头的重量，那么求一半和的背包问题，即可。
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for(int i = 0; i < stones.length; i++) {
sum += stones[i];
}
int temp = sum / 2;
int[] dp = new int[temp + 1];
for(int i = 0; i < stones.length; i++) {
for(int j = temp; j >= stones[i]; j--) {
dp[j] = Math.max(dp[j], dp[j-stones[i]] + stones[i]);
}
}
return sum - 2*dp[temp];
}
}
