一、题目内容 中等

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例1：

输入：amount = 5, coins = [1, 2, 5] 输出：4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1

示例2：

输入：amount = 3, coins = [2] 输出：0 解释：只用面额 2 的硬币不能凑成总金额 3 。

示例3：

输入：amount = 10, coins = [10]
输出：1

提示：

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000

    二、解题思路

    这是一道典型的背包问题，一看到钱币数量不限，就知道这是一个完全背包。
    但本题和纯完全背包不一样，纯完全背包是能否凑成总金额，而本题是要求凑成总金额的个数！
    注意题目描述中是凑成总金额的硬币组合数，为什么强调是组合数呢？
    例如示例一：
    5 = 2 + 2 + 1
    5 = 2 + 1 + 2
    这是一种组合，都是 2 2 1。
    如果问的是排列数，那么上面就是两种排列了。
    组合不强调元素之间的顺序，排列强调元素之间的顺序。 这一点我们在讲解回溯算法专题的时候就讲过了
    那我为什么要介绍这些呢，因为这和下文讲解遍历顺序息息相关!

回归本题，动规五步曲来分析如下：

  1. 确定dp数组以及下标的含义

dp[j]：凑成总金额 j 的货币组合数

  1. 确定递推公式

dp[j] （考虑coins[i]的组合总和） 就是所有的dp[j - coins[i]]相加。
所以递推公式：dp[j] += dp[j - coins[i]] :::info 这个递推公式大家应该不陌生了，我在讲解01背包题目的时候在 8. 目标和(494) 中就讲解了
求装满背包有几种方法，一般公式都是：**dp[j] += dp[j - nums[i]]** :::

  1. dp 数组如何初始化

首先dp[0]一定要为 1，dp[0] = 1是 递归公式的基础

为啥是递归的基础？ 你想想dp[1]的值怎么来的就知道了

从dp[i]的含义上来讲就是，凑成总金额 0 的货币组合数为 1。

  1. 确定遍历顺序

本题中我们是外层 for 循环遍历物品（钱币），内层 for 遍历背包（金钱总额）
还是外层 for 遍历背包（金钱总额），内层 for 循环遍历物品（钱币）呢？
背包理论之完全背包中讲解了完全背包的两个 for 循环的先后顺序都是可以的。但本题就不行了！
因为纯完全背包求得是能否凑成总和，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！
而本题要求凑成总和的组合数，元素之间要求没有顺序。

那么本题，两个 for 循环的先后顺序可就有说法了。
我们先来看 外层 for 循环遍历物品（钱币），内层 for 遍历背包（金钱总额）的情况。

  1. // 先遍历物品
  2. for (let i = 0; i < coins.length; i++) {
  3.   // 后遍历背包
  4.   for (let j = coins[i]; j <= amount; j++) {
  5.     dp[j] += (dp[j - coins[i]] || 0)
  6.   }
  7. }

假设：coins[0] = 1，coins[1] = 5。
那么就是先把 1 加入计算，然后再把 5 加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。
所以这种遍历顺序中dp[j]里计算的是组合数！
如果把两个 for 交换顺序，代码如下：

  1. // 先遍历背包
  2. for (let j = 0; j <= amount; j++) {
  3.   // 后遍历物品
  4.   for (let i = 0; i < coins.length; i++) {
  5.     if(j >= coins[i]) dp[j] += (dp[j - coins[i]] || 0)
  6.   }
  7. }

背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。
此时**dp[j]**里算出来的就是排列数！

  1. 举例推导 dp 数组

输入: amount = 5, coins = [1, 2, 5] ，dp状态图如下：
image.png
最后红色框 dp[amount]为最终结果。

三、具体代码

  1. /**
  2.  * @param {number} amount
  3.  * @param {number[]} coins
  4.  * @return {number}
  5.  */
  6. var change = function (amount, coins) {
  7.   const dp = new Array(amount + 1).fill(0)
  8.   dp[0] = 1
  9.   // 先遍历物品
  10.   for (let i = 0; i < coins.length; i++) {
  11.     // 后遍历背包
  12.     for (let j = coins[i]; j <= amount; j++) {
  13.       dp[j] += (dp[j - coins[i]] || 0)
  14.     }
  15.   }
  16.   return dp[amount]
  17. };

四、其他解法