1049. 最后一块石头的重量 II
思路：解题的难度在于如何转化为背包问题。本题的核心思路是让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题，和416. 分割等和子集非常像了。
首先，背包的容量target为sum/2向下取整，得到dp[target]就是分出来较小的一堆，用sum-dp[target]-dp[target]即为所求的最小差值。
代码如下：
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum=0;
for(int i:stones) sum+=i;
int target=sum/2;
int[] dp=new int[target+1];
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]);
}
}
return sum-dp[target]-dp[target];
}
}
494. 目标和
思路：这个题的思路比较难想。本题要考虑如何使表达式结果为target，即left组合 - right组合 = target。由于left + right = sum，则right = sum - left，由left - (sum - left) = target 推导出 left = (target + sum)/2 。其中target是固定的，sum是固定的，left就可以求出来。此时问题就转化为在集合nums中找出和为left的组合。
假设加法的总和为x，减法对应的总和就是sum - x，要求x - (sum - x) = target即x = (target + sum) / 2。考虑(target + sum) / 2 向下取整有没有影响，如果sum是5，target是2 的话其实就是无解的，也就是说if ((target + sum) % 2 == 1) return 0; 此时没有方案
同时，如果target 的绝对值已经大于sum，也没有方案。
由于之前的问题都是背包能装的最大价值，这个题目是刚好装满背包有多少种方法，所以dp数组的含义发生了改变，我们使用动规五部曲进行分析。
1、确定dp数组以及下标的含义
dp[j]为装满j这么大容量的包，有dp[j]种方法。
2、确定递推公式
dp[j] = dp[j] + dp[j - nums[i]] ，即：dp[j] += dp[j - nums[i]]。
不放物品i：即背包容量为j，里面不放物品i，装满有dp[j]中方法。
放物品i： 即先空出物品i的容量，背包容量为（j - 物品i容量），放满背包有 dp[j - nums[i]] 种方法。
3、dp数组如何初始化
dp[0] 同样初始为1 ,即装满背包为0的方法有一种，放0件物品。
4、确定遍历顺序
遍历物品放在外循环，遍历背包在内循环，且内循环倒序（为了保证物品只使用一次）。
5、举例推导dp数组
注意：理解递推公式非常重要，可以结合二维数组来理解。
代码如下：
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum=0;
for(int i:nums) sum+=i;
if(Math.abs(target)>sum) return 0;
if((sum+target)%2==1) return 0;
int bag=(sum+target)/2;
int[] dp=new int[bag+1];
dp[0]=1;
for(int i=0;i<nums.length;i++){
for(int j=bag;j>=nums[i];j--){
dp[j]+=dp[j-nums[i]];
}
}
return dp[bag];
}
}
474.一和零
思路：这个题目的关键是弄明白背包的重量是什么，在这个题里面背包有两个维度，一个是m 一个是n，而不同长度的字符串就是不同大小的待装物品。
动规五部曲：
1、确定dp数组以及下标的含义
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
2、确定递推公式
dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
dp[i][j] 就是 dp[i - zeroNum][j - oneNum] + 1。
在遍历的过程中，取dp[i][j]的最大值。所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
对比01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。
3、dp数组如何初始化
因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。
4、确定遍历顺序
外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！本题物品就是strs里的字符串，背包容量就是m和n。由于m,n都是物品重量的一个维度，先遍历哪个都行。
5、举例推导dp数组
代码如下：
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp=new int[m+1][n+1];
int zeroNum;
int oneNum;
for(String str:strs){
zeroNum=0;
oneNum=0;
for(char c:str.toCharArray()){
if(c=='0') zeroNum++;
else oneNum++;
}
for(int i=m;i>=zeroNum;i--){
for (int j=n;j>=oneNum;j--){
dp[i][j]=Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
}
}
}
return dp[m][n];
}
}