常见的背包问题有0 1 背包问题和完全背包问题，对于一个要装入背包的元素来说，如果他只能使用一次就是0 1背包问题，如果能使用多次则就是完全背包问题。此外这里使用的01 背包是1维的形式，1维的01 背包只能先遍历物品，再遍历背包，并且保证内层循环是倒叙的进行遍历。
类型一（能否装满背包）
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
416. 分割等和子集
题目连接：https://leetcode.cn/problems/partition-equal-subset-sum/
有人看到这个题就会说了，这哪里看着像背包问题背包在哪里，就算你把物品看成nums，背包不知道怎么获取。
但是你需要提取出四点信息才能确定这是01 背包问题
背包的体积为sum / 2
背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
背包如果正好装满，说明找到了总和为 sum / 2 的子集。
背包中每一个元素是不可重复放入。
题目中问的是分割等和的子集，就是把一个集合一分为二看是否两个子集相等就完了。
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;
int target=sum/2;
int[] dp=new int[target+1];
dp[0]=0;
for(int i=0;i<nums.length;i++){
for(int j=target;j>=nums[i];j--){
dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
}
}
return dp[target]==target;
}
}
1049. 最后一块石头的重量 II
题目连接：https://leetcode.cn/problems/last-stone-weight-ii/
顺便提一句这个题是完美世界的笔试题
题中说道随机拿出石头相撞最后要么全部撞碎，要么只剩一块，全部撞碎的情况是不是就分成两等份了？那如果剩一块呢，剩一块可以看成两份相等的石头多一块不就完了，换汤不换药。
这里还是求和然后除了一半，注意内层循环是逆序的。
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum=0;
for(int i=0;i<stones.length;i++){
sum+=stones[i];
}
int target=sum/2;
int[] dp=new int[target+1];
//dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背dp[j]这么重的石头。
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];
}
}
类型二（装满背包的方式有几种）
dp[j] += dp[j - nums[i]]
494. 目标和
题目连接：https://leetcode.cn/problems/target-sum/
思路：一部分数是正数，一部分数是负数。两部分数相加等于target
假设加法的总和为x，那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = target
x = (target + sum) / 2
此时问题就转化为，装满容量为x背包，有几种方法。
大家看到(target + sum) / 2 应该担心计算的过程中向下取整有没有影响。
有影响的！如果有余数的话组不成那就返回0；
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum=0;
for(int i=0;i<nums.length;i++){
sum+=nums[i];
}
if((target+sum)%2!=0) return 0;
int bagesize=(target+sum)/2;
if(bagesize<0) bagesize=-bagesize;
int[] dp=new int[bagesize+1];
//组成容量j有dp【j】种方法
dp[0]=1;//容量为0的组成方法就一种就是放入0
for(int i=0;i<nums.length;i++){
for(int j=bagesize;j>=nums[i];j--){
dp[j]+=dp[j-nums[i]];
}
}
return dp[bagesize];
}
}
518. 零钱兑换 II
题目连接：https://leetcode.cn/problems/coin-change-2/
完全背包解法，注意初始化dp【0】，第二层for循环从coins[i]开始
class Solution {
public int change(int amount, int[] coins) {
int[] dp=new int[amount+1];
//代表了组成amount金额所需要的硬币数
dp[0]=1;
for(int i=0;i<coins.length;i++){
for(int j=coins[i];j<=amount;j++){
dp[j]+=dp[j-coins[i]];
}
}
return dp[amount];
}
}
377. 组合总和 Ⅳ
题目连接：https://leetcode.cn/problems/combination-sum-iv/
思路：上面两个题都没有讨论关于顺序的问题，只要组成特定背包的组合，可这个题就不一样了，这个题要求的就是排列。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
如果把遍历nums（物品）放在外循环，遍历target的作为内循环的话，举一个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为nums遍历放在外层，3只能出现在1后面！
所以本题求排列，先遍历背包再遍历物品
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp=new int[target+1];
dp[0]=1;
for(int i=0;i<=target;i++){
for(int j=0;j<nums.length;j++){
if(i>=nums[j]){
dp[i]+=dp[i-nums[j]];
}
}
}
return dp[target];
}
}
70. 爬楼梯
题目连接：https://leetcode.cn/problems/climbing-stairs/
思路：看了以上的题之后现在想想这个经典的爬楼梯问题，要求走n个台阶的方法，一个可以一个也可以两个，比如爬三个台阶可以先1后2，也可以先2后1步，这不就是一个完全背包求排列的问题吗！target就是n也就是说背包的容量就是n，那么物品呢，物品就是1或者2呀，可以放1这个物品，也可以放2这个物品呀，1或者2可以用无限次，现在是不是豁然了许多。
class Solution {
public int climbStairs(int n) {
int[] dp=new int[n+1];
dp[0]=1;
for(int i=0;i<=n;i++){
for(int j=1;j<=2;j++){
if(i>=j){
dp[i]+=dp[i-j];
}
}
}
return dp[n];
}
}
类型三（装满背包最大价值）
474. 一和零
问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
题目连接：https://leetcode.cn/problems/ones-and-zeroes/
思路：在这个题提取背包思想还是我个人感觉不太好想，首先题意你想要找m个0和n个1从一个集合的子集中去找，而且这个子集的长度要求最大。
m个0和n个1可以看成是背包的最大的容量，物品呢就是字符串数组里面的每个字符串，再具体一点物品是每一个字符串里面0和1的个数，所以每个字符串0和1的个数统计是必要的，还有这是个01 背包问题只不过是二维维度的，记得第二个for循环是逆序的。
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp=new int[m+1][n+1];
//dp函数代表m个0和n个1的最大子集的长度
for(String s:strs){
char[] arr=s.toCharArray();
int zeroNum=0,oneNum=0;
for(char c:arr){
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];
}
}
类型四（求装满背包的所有物品的最小个数）
问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
322. 零钱兑换
题目连接：https://leetcode.cn/problems/coin-change/
思路：首先这是个完全背包问题（硬币无限），for循环都是正序，这里求得最小值，无所谓排列组合，然后套用公式，记得物品和背包容量的比较要看能不能装下
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp=new int[amount+1];
Arrays.fill(dp,amount+1);
dp[0]=0;
for(int i=0;i<coins.length;i++){
for(int j=coins[i];j<=amount;j++){
if(j>=coins[i]){
dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
}else{
continue;
}
}
}
return dp[amount]==amount+1?-1:dp[amount];
}
}
279. 完全平方数
题目连接：https://leetcode.cn/problems/perfect-squares/
思路：题中每个数可以用多次，完全背包问题
n就是target，那么物品呢？物品就是每个平方数，例如1,4，9,16。再看题目中的数据限制，1到10的4次方，那么100个平方数就够了。然后呢划重点最少数量！最少数量！最少数量！
class Solution {
public int numSquares(int n) {
int[] dp=new int[n+1];
int[] arr=new int[100];
for(int i=0;i<100;i++){
arr[i]=(int)Math.pow(i+1,2);
}
Arrays.fill(dp,n+1);
dp[0]=0;
for(int i=0;i<arr.length;i++){
for(int j=arr[i];j<=n;j++){
if(j>=arr[i]){
dp[j]=Math.min(dp[j],dp[j-arr[i]]+1);
}
}
}
return dp[n];
}
}