目录
问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); 对应题目如下：
问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：
518. 零钱兑换 II(opens new window)
问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，对应题目如下：
问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：
背包问题，大家都知道，有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
背包问题有多种背包方式，常见的有：01背包、完全背包、多重背包、分组背包和混合背包等等。
要注意题目描述中商品是不是可以重复放入。
即一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包，写法还是不一样的。
问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); 对应题目如下：
416.分割等和子集 (物品正序，背包倒序)
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
这道题目就是一道01背包应用类的题目，需要我们拆解题目，然后套入01背包的场景。
01背包相对于本题，主要要理解，题目中物品是nums[i]，重量是nums[i]，价值也是nums[i]，背包体积是sum/2。
class Solution {
public boolean canPartition(int[] nums) {
/**
* 1. 确定dp数组及下标含义 ：容量为j的背包，所背的物品价值最大可以为dp[j]，背包价值等于总和的一半
* 2. 递推公式 dp[j]=Math.max(dp[j],dp(j-nums[i])+nums[i])
* 3. 初始化 dp[0]=0 非零dp[]:0 只包含正整数的非空数组，所以非0下标的元素初始化为0
* 4. 遍历顺序 dp[j] 如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
* 5. 推导结果
*/
if (nums == null || nums.length == 0) {
return false;
}
int sum = 0;
for (int num : nums) {
sum += num;
}
//总和为奇数不能平分
if (sum % 2 != 0) {
return false;
}
int target = sum / 2;
int[] dp = new int[target + 1];
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]);
}
//剪枝一下，每一次完成for-loop，立即检查是否dp[target] == target
if (dp[target] == target) {
return true;
}
}
return dp[target] == target;
}
}问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：
518. 零钱兑换 II(opens new window)
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
/**
* 先物品后背包的情况下，根据递推公式，dp【j】一定是来自于外层上一次的结果，而外层上一次的结果一定是来源于上一个物品的dp数组，
所以不会出现物品2在物品1之前的情况，也就是只会出现【物品1，物品1，物品2】这种情况，而物品2不会出现在物品1之前，（不会重复）恰好对应组合问题；
* 而外层遍历背包 内层遍历物品就不一样了，每一层的dp【j】都是在固定j的情况下，把物品从头开始遍历，所以dp【j】来自于上一层的结果，
而上一层的结果又遍历了所有物品，所以这种遍历方式会出现【物品1，物品2，物品1】这种情况，恰好对应了排列问题
* 组合不强调元素之间的顺序，排列强调元素之间的顺序。
*
* 1.dp[j]：凑成总金额j的货币组合数为dp[j]
* 2.dp[j] 就是所有的dp[j - coins[i]]（考虑coins[i]的情况）相加。
* dp[j] += dp[j - coins[i]];
* 3.初始化 dp[0] = 1 下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]
* 4.遍历顺序 先物品后背包
* 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
* 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
*/
class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
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];
}
}问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，对应题目如下：
474.一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：
完全背包统一正序遍历
322.零钱兑换(最少个数) 正序 先物品再背包
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
class Solution {
/**
* 1.确定dp数组以及下标的含义
* dp[i]: 凑足总额为j所需钱币的最少个数为dp[j]
* 2.递推公式 在进行递推公式之前通常有对应的条件判断
* dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);
* 3.初始化
* dp[0]=0 dp[j]初始化成比较大的数，防止被覆盖
* 4.遍历顺序 完全背包（个数不受限制）
* 完全背包是正序遍历
求组合数就是外层for循环遍历物品，内层for遍历背包。
求排列数就是外层for遍历背包，内层for循环遍历物品。
*/
public int coinChange(int[] coins, int amount) {
//初始化dp数组为最大值
int max = Integer.MAX_VALUE;
//钱数需要的最少硬币
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
//初始化
dp[0] = 0;
for (int i = 0; i < coins.length; i++) { //遍历物品
//正序遍历：完全背包问题 每个硬币可以选择多次
for (int j = coins[i]; j <= amount; j++) {
//只有dp[j-coins[i]]不是初始最大值时，才有选择的必要
//在进行递推公式之前通常有对应的条件判断
if (dp[j - coins[i]] != max) {
//选择硬币数目最小的情况
dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);
}
}
}
//三目运算符比较好用 没有最小值就返回-1
return dp[amount]== max ? -1 : dp[amount];
}
}279.完全平方数(最小数量) 先背包后物品
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
class Solution {
public int numSquares(int n) {
/**
* 完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？
* 1.确定dp数组以及下标的含义
* dp[i]: 和为 j 的完全平方数的最少数量为dp[j]
* 2.递推公式 在进行递推公式之前通常有对应的条件判断
* dp[j] = Math.min(dp[j - i*i] + 1, dp[j]);
* 3.初始化
* dp[0]=0 dp[j]初始化成比较大的数，防止被覆盖
* 4.遍历顺序 完全背包（个数不受限制）
* 完全背包是正序遍历
* 求排列数就是外层for遍历背包，内层for循环遍历物品。
*/
// 定义：和为 i 的平方数的最小数量是 dp[i]
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
// base case
dp[0] = 0;
// 状态转移方程
for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= i; j++) {
// i - j * j 只要再加一个平方数 j * j 即可凑出 i
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
} `
}遍历顺序
01背包
在动态规划：关于01背包问题，你该了解这些！ (opens new window)中我们讲解二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
和动态规划：关于01背包问题，你该了解这些！（滚动数组） (opens new window)中，我们讲解一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。
完全背包
在动态规划：关于完全背包，你该了解这些！ (opens new window)中，讲解了纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
但是仅仅是纯完全背包的遍历顺序是这样的，题目稍有变化，两个for循环的先后顺序就不一样了。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
相关题目如下：
- 求组合数：动态规划：518.零钱兑换II(opens new window)
- 求排列数：动态规划：377. 组合总和 Ⅳ (opens new window)、动态规划：70. 爬楼梯进阶版（完全背包）(opens new window)
如果求最小数，那么两层for循环的先后顺序就无所谓了，相关题目如下：
对于背包问题，其实递推公式算是容易的，难是难在遍历顺序上，如果把遍历顺序搞透，才算是真正理解了。