思路

套模板+套之前的题的思路居然真的通过了。。。
震惊。

var change = function(amount, coins) {
    let dp =new Array(amount+1).fill(0)
    dp[0] =1 //凑0元的方法是什么都不放
    for(let i=0;i<coins.length;i++){
        for(let j=coins[i];j<=amount;j++){
            dp[j] +=dp[j-coins[i]]
        }
    }
    return dp[amount]
};

坑

这道题问的是组合数，所以 2+1+1 和1+2+1是同一种组合，两种排列！
求装满背包有几种方法，一般公式都是：dp[j] += dp[j - nums[i]];

遍历顺序很关键

普通的纯完全背包求得是能否凑成总和，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！【所以两种遍历都可以】
而本题是求凑出来的方案个数，且每个方案个数是为组合数。
假设：coins[0] = 1，coins[1] = 5。

• 外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）：

那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。

• 外层for循环遍历背包（金钱总额），内层for遍历物品（钱币）：

背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。

在求装满背包有几种方案的时候，认清遍历顺序是非常关键的。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。