题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

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

思路

很经典的题目，常规的方法是啥使用动态规划，也可以使用BFS。

针对动态规划，本次回顾将从最基本的思路写起，不断优化时间和空间，体会这类问题的思路历程，加深理解。

具体内容见代码及注释。

代码

DP三层循环 二维空间 代码一

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         int n = coins.length;
  4.         // dp[i][j]表示使用前面[0,i]种硬币，凑出金额为j使用的最少硬币数
  5.         int[][] dp = new int[n][amount + 1];
  6.         // 初始化，使用coins[0]看能出哪些金额，遍历[0,amount]如果为coins[0]的倍数，表示可以凑出，否则设定为一个不可能的大值，如amount+1
  7.         for (int i = 0; i <= amount; i++) {
  8.             dp[0][i] = i % coins[0] == 0 ? i / coins[0] : amount + 1;
  9.         }
  10.         // 外层循环为硬币，内层循环为金额，注意，也可交换
  11.         for (int i = 1; i < n; i++) {
  12.             for (int j = 1; j <= amount; j++) {
  13.                 // 先初始化为amount+1，表示没有可行方案
  14.                 dp[i][j] = amount + 1;
  15.                 // 使用当前硬币0个到t个，其中t=j/coins[i]，dp[i][j]为这t+1种方案的最小值
  16.                 for (int k = 0; k * coins[i] <= j; k++) {
  17.                     // 当前硬币使用k个，再使用前i-1种硬币凑出j - k * coins[i]，因此一共需要dp[i - 1][j - k * coins[i]] + k
  18.                     dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - k * coins[i]] + k);
  19.                 }
  20.             }
  21.         }
  22.         // 最后返回dp[n - 1][amount]，但如果其值为amount+1，表示无法凑出，需要返回-1
  23.         return dp[n - 1][amount] == amount + 1 ? -1 : dp[n - 1][amount];
  24.     }
  25. }

值得一提，外层两个循环可以交换，可以金额在外层，硬币在内层，也可以获得正确结果，代码如下：

DP三层循环 二维空间 金额在外 代码二

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         int n = coins.length;
  4.         int[][] dp = new int[amount + 1][n + 1];
  5.         dp[0][0] = 0;
  6.         for (int i = 1; i <= amount; i++) {
  7.             dp[i][0] = amount + 1;
  8.         }
  9.         for (int i = 1; i <= amount; i++) {
  10.             for (int j = 1; j <= n; j++) {
  11.                 dp[i][j] = amount + 1;
  12.                 for (int k = 0; k * coins[j - 1] <= i; k++) {
  13.                     dp[i][j] = Math.min(dp[i][j], dp[i - k * coins[j - 1]][j - 1] + k);
  14.                 }
  15.             }
  16.         }
  17.         return dp[amount][n] == amount + 1 ? -1 : dp[amount][n];
  18.     }
  19. }

DP两层循环 二维空间 代码三

代码一和二的三层循环中最内层的循环存在重复计算，可以优化，可以从数学方程推论的角度证明，看「这里」，也可以直接理解，我的理解见代码注释。

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         int n = coins.length;
  4.         int[][] dp = new int[n][amount + 1];
  5.         for (int i = 0; i <= amount; i++) {
  6.             dp[0][i] = i % coins[0] == 0 ? i / coins[0] : amount + 1;
  7.         }
  8.         for (int i = 1; i < n; i++) {
  9.             for (int j = 1; j <= amount; j++) {
  10.                 if (j >= coins[i]) {
  11.                     // dp[i - 1][j]对应不使用硬币coins[i]
  12.                     // dp[i][j - coins[i]] + 1表示先使用一个硬币coins[i]，剩下的金额j - coins[i]还使用[0,i]种硬币，那么就包含了coins[i]使用多次的可能
  13.                     dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i]] + 1);
  14.                 } else {
  15.                     dp[i][j] = dp[i - 1][j];
  16.                 }
  17.             }
  18.         }
  19.         return dp[n - 1][amount] == amount + 1 ? -1 : dp[n - 1][amount];
  20.     }
  21. }

将代码三的第一维维度增加1，可以使初始化更加简单。下面的写法也符合完全背包二维空间的常见写法。

DP两层循环 二维空间 硬币维度加1 代码四

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         int n = coins.length;
  4.         int[][] dp = new int[n + 1][amount + 1];
  5.         Arrays.fill(dp[0], amount + 1);
  6.         // 第一维度增加1后，dp[0][i]表示不使用任何硬币，因此只能凑出金额0，使用数量为0，因此dp[0][0]=0，除dp[0][0]外dp[0]的其余值都为amount+1
  7.         dp[0][0] = 0;
  8.         for (int i = 1; i <= n; i++) {
  9.             for (int j = 1; j <= amount; j++) {
  10.                 if (j >= coins[i - 1]) {
  11.                     dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
  12.                 } else {
  13.                     dp[i][j] = dp[i - 1][j];
  14.                 }
  15.             }
  16.         }
  17.         return dp[n][amount] == amount + 1 ? -1 : dp[n][amount];
  18.     }
  19. }

DP两层循环 一维空间

由于二维dp数组的每一行只和上一行有关，因此可以进行空间优化，只使用一维数组。基本就是将代码四的第一维度去掉就好。循环中322. 零钱兑换 - 图1的322. 零钱兑换 - 图2也可以去掉，更加简洁。

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         int n = coins.length;
  4.         int[] dp = new int[amount + 1];
  5.         Arrays.fill(dp, amount + 1);
  6.         dp[0] = 0;
  7.         for (int i = 1; i <= n; i++) {
  8.             for (int j = 1; j <= amount; j++) {
  9.                 if (j >= coins[i - 1]) {
  10.                     dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
  11.                 }
  12.             }
  13.         }
  14.         return dp[amount] == amount + 1 ? -1 : dp[amount];
  15.     }
  16. }

补充

这是一个完全背包问题，本题的所有代码，金额维度都必须正着遍历，因为322. 零钱兑换 - 图3依赖322. 零钱兑换 - 图4，两者位于矩阵的同一行，需要计算完后者才可以推出前者，前者在右边，后者在左边，因此需要正着遍历。