🚀 题目来源：力扣：322. 零钱兑换

题目

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

    解题

    暴力递归

    1. function coinChange(coins = [], amount = 0) {
    2. // 递归
    3. function dp(n) {
    4.   // 遇到 0，代表找到一个解，递归结束
    5.   if (n === 0) return 0;
    6.   // 如果 n < 0，代表无解
    7.   if (n < 0) return -1;
    8.   // 先设置一个比较大的数
    9.   var res = Number.MAX_SAFE_INTEGER;
    10.   // 循环所有的可能性
    11.   for (const coin of coins) {
    12.     // 递归求解
    13.     const v = dp(n - coin);
    14.     if (v === -1) continue;
    15.     res = Math.min(res, 1 + v);
    16.   }
    17.   return res;
    18. }
    19. return dp(amount);
    20. }

    添加备忘录

    ```javascript var dic = new Map();

function coinChange(coins = [], amount = 0) {

  1. function dp(n) {
  2.     if (dic.get(n)) return dic.get(n);
  3.     if (n === 0) return 0;
  4.     if (n < 0) return -1;
  5.     var res = Number.MAX_SAFE_INTEGER;
  6.     for (const coin of coins) {
  7.         const v = dp(n - coin);
  8.         if (v === -1) continue;
  9.         res = Math.min(res, 1 + v);
  10.     }
  11.     dic.set(n, res);
  12.     return res;
  13. }
  14. return dp(amount);

}

  1. <a name="2YFEF"></a>
  2. ## DP数组
  3. ```javascript
  4. function coinChange(coins = [], amount = 0) {
  5.     var dp = new Array(amount + 1).fill(amount + 1);
  6.     dp[0] = 0;
  7.     for (let i = 0; i < dp.length; i++) {
  8.         for (const coin of coins) {
  9.             if (i - coin < 0) continue;
  10.             dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
  11.         }
  12.     }
  13.     return (dp[amount] == amount + 1) ? -1 : dp[amount];
  14. }