代码随想录 (programmercarl.com)
完全背包的物品数量不受限制（正序遍历物品），0-1背包每个物品只能使用一次（倒序遍历背包）
完全背包两个for循环可以颠倒顺序，一维0-1背包问题只能先遍历物品再遍历背包。
类似于前面0-1背包的494.目标和问题
1.确定dp数组以及下标的含义
dp[j]：凑成总金额j的货币组合数为dp[j]
2.确定递推公式
有多少种方法用的都是这个递推公式：dp[j] += dp[j - coins[i]];
3.dp数组如何初始化
dp[0] = 1是 递归公式的基础，如果dp[0] = 0 的话，后面所有推导出来的值都是0了。
后台测试数据是默认，amount = 0 的情况，组合数为1。
4.确定遍历顺序
不同于纯完全背包问题，遍历顺序两个for循环可以调换顺序，此处不可以。
纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行。而本题要求凑成总和的组合数，元素之间明确要求没有顺序。所以纯完全背包是能凑成总和就行，不用管怎么凑的。
但是本题是求凑出来的方案个数，且每个方案个数是为组合数。
所以本题就需要注意遍历顺序，以下分情况讨论，以amount=5和coins=[1,2,5]为例：
1）先遍历物品再遍历背包：
物品按照遍历顺序出现{1,2}，不会出现{1,2}{2,1}同时出现的情况，即得出的是组合数。
for (int i = 0; i < coins.size(); i++) { // 遍历物品
for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
dp[j] += dp[j - coins[i]];
}
}2）先遍历背包再遍历物品：
遍历背包后物品每次都会再重新遍历一遍，会出现{1,2}{2,1}同时出现的情况，即得出的是排列数。
for (int j = 0; j <= amount; j++) { // 遍历背包容量
for (int i = 0; i < coins.size(); i++) { // 遍历物品
if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
}
}打印结果：
| dp[j] | j = 0 | 1 | 2 | 3 | 4 | 5 |
| i = 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 2 | 3 i = 0: dp[3] += dp[3-1]==>dp[3] = 2==>[1,1,1][1,2] i = 1: dp[3] += dp[3-2]==>dp[3] = 2 + 1 = 3==>[2,1] 此处j = 3的情况中，就出现了[1,1,1][1,2][2,1] 所以为排列数，不符合题意 | ||
| 2 |
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++) {
//注意j的起始大小，回顾dp[j]含义可知，j为背包容量，
//要确保其大于物品的重量，即需要从coins[i]开始遍历，而不是coins[0]
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
}注意j的起始大小，回顾dp[j]含义可知，j为背包容量，要确保其大于物品的重量，即需要从coins[i]开始遍历，而不是coins[0]。
1.确定dp数组以及下标的含义
dp[i]：凑成目标正整数为i的排列个数为dp[i]
2.确定递推公式
有多少种方法用的都是这个递推公式：dp[j] += dp[j - coins[i]];
3.dp数组如何初始化
题目中说给定目标值是正整数，?所以dp[0] = 1是没有意义的，此处的初始化仅仅是为了推导递推公式。
4.确定遍历顺序
求的是排列数，所以选择先遍历背包再遍历物品的顺序。
如果求组合数就是先物品再背包，如果求排列数就是先背包再物品。
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] >= 0){
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
}【拓展爬楼梯】
原始==一步只能爬1，2个台阶；进阶==一步可以爬m个台阶，到楼顶有多少种爬楼方式，代码和本题一致，求解排列数。