【LeetCode精选TOP面试题】322-零钱兑换

LeetCode 原题链接

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

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

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

动态规划解法

思路

dp[i] 表示组成 i 所需的最少硬币数。

对于 coins = [1, 2, 5]; amount = 11;

假设最后一枚硬币取的是1，则 dp[i] = dp[11 - 1] + 1 = dp[10] + 1，即

假设最后一枚硬币取的是2，则 dp[i] = dp[11 - 2] + 1 = dp[9] + 1

假设最后一枚硬币取的是5，则 dp[i] = dp[11 - 5] + 1 = dp[6] + 1

取最小值作为 dp[i] 的值，dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)

复杂度

复杂度

• 时间复杂度：O(n*m)，n 为总金额，m 为硬币种类，在计算组成每一个小于 n 的金额所需的最少硬币数时都要遍历一遍硬币数组。
• 空间复杂度：O(n)。

代码

var coinChange = function (coins, amount) {
  if (amount === 0) {
    return 0;
  }

  const dp = new Array(amount + 1).fill(Infinity);
  const minCoins = Math.min(...coins);

  if (amount < minCoins) {
    return -1;
  }

  dp[0] = 0;

  for (let i = 1; i <= amount; i++) {
    for (let j = 0; j < coins.length; j++) {
      if (i - coins[j] >= 0) {
        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
};

let result = coinChange([1, 2, 5], 11);
console.log(result);

参考

JS 零钱兑换 动态规划算法详解