【算法-LeetCode】322. 零钱兑换（动态规划；博采众长的完全背包问题详解；二维数组；滚动数组）_换零钱算法

322. 零钱兑换 - 力扣（LeetCode）

发布：2021年8月15日20:09:47

问题描述及示例

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

示例 2：
输入：coins = [2], amount = 3
输出：-1

示例 3：
输入：coins = [1], amount = 0
输出：0

示例 4：
输入：coins = [1], amount = 1
输出：1

示例 5：
输入：coins = [1], amount = 2
输出：2

提示：
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

我的题解

这是我在LeetCode上碰到的第一个背包问题，一开始是真的没有背包问题这个模型的概念，虽然通过【相关标签】的提示知道了要用可以用动态规划，但是一开始是真的想不出思路，完全无法在动态规划这条路上迈开步子……后来我经过了下面的成功前的尝试后发现自己确实是无能为力了，于是取看了相关的解析，但是这一看就是两三天啊，现在我算是用动态规划把这道题给做懂了，但是真的没有百分百的信心说下次碰到动态规划的题目还能解决，诶……到时候再做研究吧……

成功前的尝试

一开始，因为我压根就没有接触过背包问题，所以自然也不会往那个方向思考，虽说题目的标签提示我可以用动态规划做，但是我一直没有思路，没看标签前我还想着是不是用所谓的【贪心算法】解决，也就是说，用局部最优解推导或堆叠出整体最优解，但是也没思路。后来去食堂吃饭的路上，根据示例，我就突然有了下面的这个想法。回来后就写了出来。

思路很简单，我心想既然要用最少的硬币凑足规定数额，那应该是要尽量先用面额最大的硬币吧。如果最大额的硬币不能刚好凑齐，那就用次大额的硬币凑剩余的部分，如果还是不能刚好凑齐，那就再用面额更小的硬币去凑剩余的部分，重复上面的过程，直到刚好凑到指定数额。下面的pocket就是用来装硬币的空袋子，它的值表示的是当前袋子里有多少枚硬币，其值初始化为0，amount则用来记录当前状况下，要凑齐指定数额的话，还要凑多少面额，所以它是逐渐减小的。详解请看下方注释。

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
  // 如果一开始要凑的面额就是0的话，按题目要求直接返回0
  if(amount === 0) {
    return 0;
  }
  // 初始化pocket口袋中装了0枚硬币，遍历完成后，这里面存的就是最终结果
  let pocket = 0;
  // 取用硬币前要先对硬币面额按降序排列，这一步很关键
  coins.sort((a, b) => b - a);
  // 遍历可供选择的硬币，先取用面额最大的
  for(let i = 0; i < coins.length; i++) {
    // 先尝试尽量用面额大的硬币凑满，这样可以保证pocket尽可能小，floor函数用来向下取整
    pocket += Math.floor(amount / coins[i]);
    // 用大面额的硬币凑完后，算剩下要凑的数额就是对amount自身做取余操作
    amount = amount % coins[i];
  }
  // 遍历完后，如果剩余要凑的面额刚好为0则说明所提供的硬币刚好可以凑足指定数额
  if(amount === 0) {
    return pocket;
  }
  // 如果amout不为0，则说明所提供的硬币不能刚好凑足指定数额，按题目要求返回-1
  return -1;
};

提交记录
50 / 188 个通过测试用例
状态：解答错误
时间：2021/08/12 18:27
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

可以看到上面的想法看起来确实很美好，而且我将几个用例代入之后都可以返回正确结果，于是我满怀希望地将代码提交，结果确实解答错误，显示的未通过的用例是：

coins = [186,419,83,408]
amount = 6249

我按照程序的思路开始演算，发现：6249 = 419 × 14 + 408 × 0 + 186 × 2 + 11，于是pocket = 14 + 0 + 2 = 16，amount = 11，所以最后返回-1，也就是说我的程序判断上面提供的硬币组合不能刚好凑齐6249，我仔细思考，试图找出错误在哪儿，然后进行修改。但是思考中我恍然发现自己的思路根本就是不合逻辑的！而且错的非常明显。

题目是要求从提供的几种面额且数量不限的硬币中找出一种组合，使得其面额总值为指定数额，且要求该组合中的硬币数量最少。问题就出在这里，我是把【硬币数量最少】这个要求的优先级放在前面，而后才是考虑了【能不能刚好凑齐指定数额】，这与题意不符。所以我的程序的逻辑就是：一个组合要么不能满足凑齐指定数额的要求，要么就是在保证最大限度地使用了面额较大的硬币的前提下刚好能够凑齐指定数额。然鹅，事实上可能存在某种组合，这个组合能够凑齐指定面额，但是这个组合中可能为了满足凑齐指定面额这个先决要求而没有保证一定是最大限度地使用了面额较大的硬币。这就导致了不合题意的情况发生。

所以说，得先考虑能不能凑齐指定面额，然后再考虑在那些候选的组合中选出一个硬币数最少的。

我的题解1（动态规划：二维dp数组）

处于对性能的考虑，一般来说，我们都会把背包问题中二维的dp数组简化为一维数组，这也是下面的【有关参考】中所提到的滚动数组：【微信公众号：代码随想录 2021-01-19】动态规划：关于01背包问题，你该了解这些！（滚动数组）。

但是，我觉得先理解背包问题的二维数组解法再通过所谓的“滚动数组”操作来将二维简化为一维，一上来就用一维的数组感觉有点难理解。虽然一维的解法确实更简洁优雅，但是却不是很方便逐步分析。其实我用文字讲解也不是很形象，最好的方式是用纸笔将某个用例代入其中一步步推导出每个dp[i][j]，并且配合开发者工具中的逐步调试功能逐步验证自己的推导过程。如果要做动态图的话就太繁琐了，不知道能不能尝试在iPad上录屏，将整个过程录下来。

毕竟还是在动态规划的范畴内，所以基本的套路还是一样的，可以参考下方的链接：

参考：【算法-LeetCode】53. 最大子序和_赖念安的博客-CSDN博客

• 首先是确定dp数组的下标含义。dp[i][j]表示在coins[0] ~ coins[i]这些面额的硬币中选出若干枚硬币以凑满指定的数额j时所花费的最少硬币数。

• 然后是初始化dp数组。这里其实要和状态转移方程的确定一起考虑。首先根据题意和示例可以确定dp[i][0]应该被初始化为0，即二维数组的第一列应该被初始化为0。然后是第一行，也就是dp[0][j]的初始化，因为状态转移方程中用到了dp[i-1][xxxx]。

• 接着确定状态转移方程。首先是考虑两个维度：是否取用coins[i]和能否取用coins[i] ，也就是①我们当前可能压根不能取用coins[i]，这是被动不取用coins[i]；或者②当前我们能够取用coins[i]但是我们根据题意限制推测出当前不取用coins[i]更好，这是主动不取用coins[i]。

  如果我们让：dp[i][j] = dp[i-1],[j]，那就是我们主动不去取用coins[i]或者当前背包容量j不足以装下coins[i]时所花费的最少硬币数（反正是我们主动不去取用coins[i]）；
  
  如果我们让：dp[i][j] = dp[i - 1][j - coins[i]] + 1，那就是我们先回头看看当初在被动（因为此时赋值符号右边的二维数组的第一维的下标为i-1）不能取用coins[i]的情况下时所花费的最少硬币数是多少（假设为x），因为我们是通过j - coins[i]完成【回头看看】这个操作的，所以此时背包中其实是预留了一块刚好够把coins[i]放进当前容量为j的背包的空间的，相当于事先放了一个面额为coins[i]的硬币进去占位置。这时只要在x的基础上加上这枚占位置的硬币，就是当前遍历情况下的所要花费的最少硬币数：x+1。（有种回头看看在当初没有提供coins[i]时，日子是咋过的那种感觉）
  
  如果我们让：dp[i][j] = dp[i][j - coins[i]] + 1，那就是我们先回头看看当初在主动（因为此时赋值符号右边的二维数组的第一维的下标为i）不去取用coins[i]的情况下时所花费的最少硬币数是多少（假设为y）。和上面同理，因为我们事先放了一个面额为coins[i]的硬币进去占位置。这时只要在y的基础上加上这枚占位置的硬币，就是当前遍历情况下的所要花费的最少硬币数：y+1。（有种回头看看在当初已经提供coins[i]时，日子是咋过的那种感觉）
  
  最后就是按照题目要求，我们要找在凑齐指定数额的前提下花费的最少硬币数，所以在上面三种情况中取一个最小值作为当前的dp[i][j]的值。
  

  所以，最后的状态转移方程就是：

  dp[i][j] = Math.min(Math.min(dp[i - 1][j - coins[i]], dp[i][j - coins[i]]) + 1, dp[i - 1][j])

  但是这样不利于阅读理解，所以我把内层的那个Math.min()提取了出来，用一个中间变量temp来保存：

  let temp = Math.min(dp[i - 1][j - coins[i]], dp[i][j - coins[i]]);
dp[i][j] = Math.min(temp + 1, dp[i - 1][j]);

• 接着最好是像我下面画的表格一样照着程序逻辑一步步填充表格中的单元格并配合Chrome开发者工具逐步调试的功能对整个过程进行观察。

其他详解请看下方注释。

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
function coinChange(coins, amount) {
  // 初始化整个二维dp数组，即：用Infinity填充整个二维数组，
  // 这里碰上自己挖的坑，详解见下方【补充1】
  let dp = Array.from({ length: coins.length }).map(
    () => Array.from({ length: amount + 1 }).fill(Infinity)
  );
  // 背包问题一般都是要手动初始化第一行和第一列的，因为下面会用到dp[i-1][xxx]这类的操
  // 作，如果不事先特地初始化一下，可能会下标溢出。但是不同的背包问题初始化操作可能不一样
  // 初始化第一列：dp[i][0]（全为0，这里是直接根据题意推断的）
  for (let i = 0; i < coins.length; i++) {
    dp[i][0] = 0;
  }
  // 初始化第一行：dp[0][j]，详解见下方【补充2】
  for (let j = 1; j <= amount; j++) {
    if (j % coins[0] === 0) {
      dp[0][j] = j / coins[0];
    }
  }
  // 开始遍历填充dp数组，也就是计算dp[i][j]
  // 这道题中不涉及排列或组合的问题，所以可以随意选择先遍历什么，
  // 那就先开始遍历硬币（外层for循环），再遍历背包容量（内层for循环）
  for (let i = 1; i < coins.length; i++) {
    for (let j = 1; j <= amount; j++) {
      // 先要判断当前背包容量 j 和 硬币面额大小 coins[i] 的大小，下面这个if判断相当于是
      // 把 ＜coins[i] 的 j 值所对应的dp[i][j]做一个填充，详解见下方【补充3】
      if (j < coins[i]) {
        dp[i][j] = dp[i - 1][j];
        continue;
      }
      // 因为题目要求最少的硬币数，所以下面这个temp变量是用来存储在coins[i]可选和不可选
      // 这两种情况下都不取用coins[i]所花费的硬币数的较小值
      let temp = Math.min(dp[i - 1][j - coins[i]], dp[i][j - coins[i]]);
      // temp+1表示取用coins[i]的情况下装满容量为j的背包所需的最少硬币数，
      // dp[i-1][j]表示coins[i]不可选的情况下装满容量为j的背包所需的最少硬币数，
      // dp[i][j]应该取其中的较小值
      dp[i][j] = Math.min(temp + 1, dp[i - 1][j]);
    }
  }
  // 遍历完成后，二维数组中右下角的元素值即为最终结果，如果该值为一开始初始化的Infinity，
  // 说明提供的硬币不能刚好凑齐指定数额，所以返回-1
  if(dp[coins.length - 1][amount] === Infinity) {
    return -1;
  }
  // 否则返回右下角元素作为最终结果
  return  dp[coins.length - 1][amount];
}


提交记录
188 / 188 个通过测试用例
状态：通过
执行用时：476 ms, 在所有 JavaScript 提交中击败了5.10%的用户
内存消耗：43.6 MB, 在所有 JavaScript 提交中击败了27.05%的用户
时间：2021/08/15 20:12
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

相关的图示：（在博客上看着可能会比较小，可以下载之后查看）

上面的coins数组我特意用两种不同的顺序代入程序进行推导，可以好好观察其中的差别和相同之处。最好是能够在谷歌的开发者工具中进行逐步调试来观察过程。当然自己也可以再让coins为[5,2,1]，然后按照程序逻辑填充上面的表格，最后右下角的结果是一样的。

2021年8月16日01:06:26，太晚了，先睡了，明天再来更新……

更新：2021年8月16日12:24:47

昨天太晚了，用Excel画上面的图示还花了点时间。早上七点多的时候楼上有施工队在用钻地板，震得脑花都散了，室友说他们是被吵醒的，我说自己是被吓醒的，因为睡梦中隐约听见一连串恶毒的诅咒：秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃秃……

感谢施工大叔的叫醒服务！没办法，上午只能去自习室避避了，这个时候大叔们应该去吃饭了，开始补一下剩下的东西吧。

相关补充

• 【补充1】这里自己给自己挖了一个坑，详细可以看我的这篇博客：【JavaScript基础-二维数组】JavaScript修改二维数组的某个元素时，其上下元素也受到影响_赖念安的博客-CSDN博客
• 【补充2】上面说了，具体问题中的第一行和第一列的初始化操作可能有所不同。在本题中，初始化第一行就是在只取用coins[0]的情况下，凑齐容量为j的背包最少要用几枚硬币。因为当前只有一枚硬币coins[0]可供取用，那就直接用当前容量j除以硬币面额即可，要是能整除，则将整除结果作为dp[0][j]的结果；要是不能整除，说明只用coins[0]这一种面额的硬币没法刚好填满容量为j的背包。
• 【补充3】可以这样理解：因为当前硬币的面额太大了，没法放进背包中，所以直接不考虑将面额为coins[i]的硬币放入背包的情况。dp[i - 1][j]表示的是在面额为coins[i]的硬币不可选的状态下要装满容量为j的背包所需的最少硬币数，而现在coins[i]是可选的，但是奈何coins[i]面额太大了，所以我们不选用它。所以现在是可以选，但是我们不选，而之前是压根不能选，所以有dp[i][j] = dp[i - 1][j]，千万不要忘记continue，否则辛苦算的dp[i][j]会被后面的语句给改写。其实这里的这个if判断就是对应了上面我画的Excel示意图中的浅绿色部分，仔细观察可以发现浅绿色单元格的值就是它正上方那个单元格的值。
• 【补充4】上面图中白色和浅绿色的单元格其实都是在程序中的双层for循环中完成填充的。其中浅绿色部分对应if判断。

好了，二维数组的解法差不多就到这里了。其实配上视频或者动态图理解会更好，但是我就不花那个功夫了，毕竟写博客的目的主要还是给自己讲解过程，以便自己日后能够快速复习，上面的内容已经差不多可以让我把此时的思考过程给复现出来了，所以就不多做复杂的工作了。

我的题解2（动态规划：一维dp数组）

上面提到了滚动数组的概念，相信只要对上面二维数组的解法有了完全的掌握，看上面的那个滚动数组的概念应该会轻松很多。

二维转一维

我是这么理解由二维解法转向一维解法的过程的：我们是采用先遍历硬币再遍历背包容量的方法，所以不妨假设我们现在正在遍历（或者说填充）二维数组的第二行，也就是计算dp[1][j]。其实我们计算dp[i][j]时用到的数据就三个：dp[i - 1][j - coins[i]]、dp[i][j - coins[i]]和dp[i-1][j]。比如下图中，我要计算dp[1][5]，那么我就要用到dp[0][3]、dp[1][3]和dp[0][5]。

首先，我们对dp[i - 1][j - coins[i]]和dp[i][j - coins[i]]先做Math.min操作得到了temp，然后我们再对temp+1和dp[i-1][j]做Math.min操作得到dp[i][j]。在上图中就是先取得了temp =Math.min(dp[0][3], dp[1][3]) = Math.min(3, 2) = 2，然后算得dp[1][5] = Math.min(temp+1, dp[0][5]) = Math.min(3, 5) = 3。

那完全可以先把temp的值赋给dp[i - 1][j - coins[i]]，再做temp+1和dp[i-1][j]的比较，这就相当于是直接利用第一行的数组进行操作，随着遍历的深入，第一行的数据将被不断地逐位重新赋值，最后的结果就是当最后一枚硬币被遍历完后，第一行的末位元素的值就是我们想要的结果。如果通过Chrome开发者工具观察一维数组解法中的dp数组，就可以发现，每当外层for循环完成了一次迭代，dp数组中的值就和上面表格中相对应的行的数据是一样的。

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
  // 如果amount为0，按题目要求应该直接返回0，其实解法一中也可以加入这个判断以提高效率
  if(amount === 0) {
    return 0;
  }
  // 创建一个长度为amount+1的一维数组，并用Infinity填充
  let dp = Array.from({length: amount + 1}).fill(Infinity);
  // 初始化dp数组
  dp[0] = 0;
  // 和上面一样，先遍历硬币面额，在遍历背包容量
  for(let i = 0; i < coins.length; i++) {
    for(let j = 1; j <= amount; j++) {
      // 只有在当前背包容量足够装得下当前遍历的硬币时才能考虑是否取用当前硬币
      // 这的逻辑和上面的逻辑一样，只是巧妙地避开了当j<coins[i]时特意计算相应dp[j]的情况
      // 详解看下方【补充5】
      if(j >= coins[i]) {
        dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
};

提交记录
188 / 188 个通过测试用例
状态：通过
执行用时：204 ms, 在所有 JavaScript 提交中击败了18.86%的用户
内存消耗：43.8 MB, 在所有 JavaScript 提交中击败了22.15%的用户
时间：2021/08/16 14:13
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

相关补充

• 【补充5】因为之前提到浅绿色部分单元格的操作其实就是把正上方的那个单元格的值抄下来，而这里的j >= coins[i]这个if判断恰巧避开了对那些浅绿色单元格的重新赋值操作，而又因为我采用一维数组，所以实际上等效于程序已经隐式地完成了那部分浅绿色单元格的操作，简直是妙妙子碰上了绝绝子。

理论上来说，这种一维数组的解法在空间上的表现应该要比二维数组好，但是从上面的结果来看，好像和预期不一样，LeetCode的OJ系统也受到网络等因素的影响，不必太在意，关键是理解了原理。

可以看到，一维数组的解法更加的简洁高效，①首先是不用特意事先对第一行和第一列做初始化了；②其次是不用特意在coins[i] > j的情况下对相应的数组元素做填充（也就是上面提到的浅绿色部分的单元格所对应的那个操作）；③也不用特意通过中间变量temp来计算最终结果。

有关背包问题的题目往往都不是以纯粹的背包问题来考察，而是经过一番包装，这道题就是把完全背包问题中的背包换成了amount这个需要凑齐的指定数额，其中的原来还是相通的。至于其他的相关问题，比如物品和背包容量的遍历先后问题、遍历背包容量时由前到后和由后到前的问题、状态转移方程中的下标取用问题等等都是更具具体的题目要求进行分析的。总的来说还是遵循下面总结的动态规划的那几个步骤的。

参考：【算法-LeetCode】53. 最大子序和_赖念安的博客-CSDN博客

【更新结束】

总结

更新：2021年8月16日16:25:12

LeetCode上有题友做了相关的总结，感觉应付题目应该是可以了，但是我没有做相关的验证，以下仅以学习为目的做出分享：

参考：一篇文章吃透背包问题！（细致引入+解题模板+例题分析+代码呈现） - 零钱兑换 - 力扣（LeetCode）

首先是背包分类的模板：
1、0/1背包：外循环nums,内循环target,target倒序且target>=nums[i];
2、完全背包：外循环nums,内循环target,target正序且target>=nums[i];
3、组合背包(考虑顺序)：外循环target,内循环nums,target正序且target>=nums[i];
4、分组背包：这个比较特殊，需要三重循环：外循环背包bags,内部两层循环根据题目的要求转化为1,2,3三种背包类型的模板

然后是问题分类的模板：
1、最值问题： dp[i] = max/min(dp[i], dp[i-num]+1)或dp[i] = max/min(dp[i], dp[i-num]+nums);
2、存在问题(bool)：dp[i]=dp[i]||dp[i-num];
3、组合问题：dp[i]+=dp[i-num];

非常感谢题友【星晴pro - 力扣（LeetCode）】的总结解析与分享！

【更新结束】

官方题解

更新：2021年7月29日18:43:21

因为我考虑到著作权归属问题，所以【官方题解】部分我不再粘贴具体的代码了，可到下方的链接中查看。

更新：2021年8月15日20:18:11

参考：零钱兑换 - 零钱兑换 - 力扣（LeetCode）

【更新结束】

也有其他优秀的题解可能更易于理解，详情参照下面的【有关参考】。

有关参考

更新：2021年8月15日20:21:15

【LeetCode中的其他题解参考】：
参考：Java 递归、记忆化搜索、动态规划 - 零钱兑换 - 力扣（LeetCode）
参考：一篇文章吃透背包问题！（细致引入+解题模板+例题分析+代码呈现） - 零钱兑换 - 力扣（LeetCode）（建议收藏）
参考： 「代码随想录」带你学透完全背包！【322. 零钱兑换】 - 零钱兑换 - 力扣（LeetCode）
参考：（LeetCode题友视频讲解）「零钱兑换」JavaScript 动态规划 解法 - 零钱兑换 - 力扣（LeetCode）

更新：2021年8月15日20:26:33

【B站相关讲解视频】：
参考：JavaScript算法题：完全背包问题_哔哩哔哩_bilibili
参考：【动态规划】背包问题_哔哩哔哩_bilibili
参考：b站最清楚讲解动态规划基础-学不会01背包你来打我！_哔哩哔哩_bilibili
参考：带你学透0-1背包问题！| 关于背包问题，你不清楚的地方，这里都讲了！| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili

更新：2021年8月15日20:29:25

【其他讲解博客】：
参考：代码随想录-背包问题理论基础完全背包（建议收藏）
参考：【微信公众号：代码随想录 2021-02-03】动态规划： 给我个机会，我再兑换一次零钱
参考：【微信公众号：代码随想录 2021-01-19】动态规划：关于01背包问题，你该了解这些！（滚动数组）
参考：【微信公众号：代码随想录 2021-01-25】动态规划：目标和！
参考：动态规划：完全背包问题_xylitolz的博客-CSDN博客（建议收藏）
参考：AcWing 3. 完全背包问题 - AcWing

参考：【算法-LeetCode】53. 最大子序和_赖念安的博客-CSDN博客
参考：Array.prototype.map() - JavaScript | MDN
参考：Array.from() - JavaScript | MDN