先总体介绍一下0-1背包和完全背包的区别
主要是01背包和完全背包（背包九讲里面的其他背包问题，都是竞赛级别的，leetcode上面没有）
01背包就是：背包存在一个最大容量V，每个物品有两个参数：体积w和价值v，目的是在不超过背包最大容量的前提下，取出物品的价值最大
如果每个物品的数量只有1个，那就是01背包问题
如果每个物品的数量是无限的，那就是完全背包问题
leetcode上没有纯01背包的问题，都是01背包应用方面的题目，也就是需要转化为01背包问题。
动态规划要搞清楚三个问题：
（1）dp[i][j]的含义
（2）状态转移方程
（3) dp数组开多大，最后返回什么，一般是返回数组的最后一个元素
物体的数量是m（m个物体），背包可以装的最大容量为w，开一个dp[m+1][w+1]的二维数组
第i件商品的重量为weight[i-1],重量为values[i-1]
状态转移方程就是考虑第i个物品放不放的进去
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i-1]] + value[i-1]);
前者是不拿第i个物品，后者是拿第i个物品（拿前i-1个物品的价值+第i个物品的价值就是拿前i个物品的价值，这里要主要第i个物品的重量是weight[i-1],价值是value[i-1]）代码实现：
传入三个参数，weight数组，value数组，bagweight(背包能装的最大重量)
物品有weight[]数组和values[]数组
背包的能装的最大重量为bageweight
public int help(int[] weight,int[] value,int bagweight)
{
int[][] dp=new int[weight.length+1][bagweight+1];
// weight数组的大小 就是物品个数
for(int i = 1; i < weight.length+1; i++) // 遍历物品
{
for(int j = 1; j < bagweight+1; j++) // 遍历背包容量
{
if (weight[i-1]>j) //如果光是第i个物品本身的重量已经超过了背包容量，这说明肯定不能取第i个物品，第i个物品对应的是weight[i-1]和value[j-1]
{
dp[i][j] = dp[i - 1][j];
}
else
{
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i-1]] + value[i-1]);
//前者是不拿第i个物品，后者是拿第i个物品（拿前i-1个物品的价值+第i个物品的价值就是拿前i个物品的价值，这里要主要第i个物品的重量是weight[i-1],价值是value[i-1]）
}
}
}
return dp[weight.length][bagweight];
}这两个问题都是横轴是可以选的数，纵轴是要拼成的target
不要想压缩到一维数组，掌握二维数组的解法就够了
这两种背包问题就是二维dp问题，把二维表格画出来基本就能解决了
力扣416 分割等和子集
这个问题就转化成，问你这个集合的子集中，是否存在一个子集，它的所有元素之和等于target
其中 dp[i] 表示是否可以找到一个子集，使得其元素和等于 i
step1：开二维dp数组:int[][] dp=new int[nums.length][]，确定dp[i][j]的含义
step2：第一行，只用nums[i]这一个数，肯定只能拼出nums[i]，所以：
for(int j=0;j<=target;j++)
{
if(j==nums[0])
{
dp[0][j]=true;
}
}
step3：状态转移方程
dp[i][j]表示从nums[0]-nums[i]中这些数中能否拼成j
（1）当nums[i]=j时，表示nums[i]一个数就可以拼出j，所以dp[i][j]一定是true
（2）如果nums[i]<j，表示nums[i]这个数小于j，那么dp[i][j]=dp[i-1][j-nums[i]],也就是说前面的数能拼成j-nums[j]，那么加上nums[i]这个数，就能拼成j
（3）如果dp[i-1][j]=true,表示不用nums[i]这个数，也能拼出j，那么说明dp[i][j]一定是true
完整代码如下：
class Solution
{
public boolean canPartition(int[] nums)
{
if(nums.length==0) return false;
int n=nums.length;
int sum=0;
for(int num:nums)
{
sum=sum+num;
}
//总和为奇数，那肯定是不能分成两个和相等的子集
if(sum%2!=0) return false;
int target=sum/2;
boolean[][] dp=new boolean[nums.length][target+1];
for(int j=0;j<=target;j++)
{
if(j==nums[0])
{
dp[0][j]=true;
}
}
//从第一行开始,然后是第二行，第三行.....
for(int i=1;i<nums.length;i++)
{
for(int j=0;j<=target;j++)
{
if(nums[i]==j) dp[i][j]=true;
if(nums[i]<j) dp[i][j]=dp[i-1][j-nums[i]]||dp[i-1][j];
if(nums[i>j]) dp[i][j]=dp[i-1][j];
}
}
return dp[nums.length-1][target];
}
}public class Knapsack {
public static int knapsack(int[] w, int[] v, int V) {
int n = w.length;
int[][] dp = new int[n + 1][V + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= V; j++) {
for (int k = 0; k * w[i - 1] <= j; k++)//此时背包容量大小为j
{
dp[i][j] = Math.max(dp[i-1][j], dp[i - 1][j - k * w[i - 1]] + k * v[i - 1]);
//前者是不加入第i件物品，后者是加入第i件物品（第i件物品的重量是weight[i-1],价值是value[i-1]）
}
}
}
return dp[n][V];
}
}
力扣322 零钱兑换（每种硬币的数量是无限的）
定义 dp[i][j]为考虑前 i件物品，凑成总和为 j 所需要的最少硬币数量
class Solution
{
public int coinChange(int[] coins, int amount)
{
int n=coins.length,m=amount;
int INF=Integer.MAX_VALUE;
int[][]dp=new int[n+1][m+1];
//初始化，amount=0
for (int i = 1; i <= n ; i++)
{
dp[i][0]=0;
}
//初始化,coins=0
for (int i = 1; i <= amount; i++)
{
dp[0][i]=INF;
}
for (int i = 1; i <=n ; i++)
{
for (int j = 1; j <=m ; j++)
{
dp[i][j]=dp[i-1][j];
for (int k = 1; k*coins[i-1]<=j ; k++)
{
if(dp[i-1][j-k*coins[i-1]]!=INF)
{
dp[i][j]=Math.min(dp[i-1][j-k*coins[i-1]]+k,dp[i][j]);
}
}
}
}
return dp[n][m]==INF?-1:dp[n][m];
}
}class Solution {
static int N = 0x3f3f3f3f;
public int coinChange(int[] coins, int amount) {
int n = coins.length;
int[][] f = new int[n + 1][amount + 1];
for(int i = 0; i < n + 1; i ++){
Arrays.fill(f[i], N);
}
for(int i = 0; i < n + 1; i ++) f[i][0] = 0;
for(int i = 1; i <= n; i ++){
for(int j = 0; j <= amount; j ++){
int maxCount = j / coins[i - 1];
for(int k = 0; k <= maxCount; k ++){
f[i][j] = Math.min(f[i][j], f[i - 1][j - coins[i - 1] * k] + k);
}
}
}
if(f[n][amount] == N) return -1;
else return f[n][amount];
}
}