Pengjielee's blog

题目

给定不同面额的硬币 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

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

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

提示：

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

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

JS实现

1、递归

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  if (coins.length === 0) {
    return -1;
  }

  let result = Number.MAX_SAFE_INTEGER;

  const find = (amount, count) => {
    if (amount < 0) {
      return;
    }
    if (amount === 0) {
      result = Math.min(result, count);
    }
    for (let i = 0; i < coins.length; i++) {
      find(amount - coins[i], count + 1);
    }
  };

  find(amount, 0);

  if (result === Number.MAX_SAFE_INTEGER) {
    return -1;
  }

  return result;
};

2、记忆化递归

var coinChange = function (coins, amount) {
  if (coins.length === 0) {
    return -1;
  }

  const memo = new Array(amount).fill(0);

  //memo[n] 表示钱币n可以被换取的最少的硬币数，不能换取就为-1
  const find = (amount) => {
    if (amount < 0) {
      return -1;
    }
    if (amount === 0) {
      return 0;
    }
    if (memo[amount - 1] != 0) {
      return memo[amount - 1];
    }
    let min = Number.MAX_SAFE_INTEGER;

    for (let i = 0; i < coins.length; i++) {
      let res = find(amount - coins[i]);
      if (res >= 0 && res < min) {
        min = res + 1;
      }
    }
    memo[amount - 1] = min === Number.MAX_SAFE_INTEGER ? -1 : min;

    return memo[amount - 1];
  };

  return find(amount);
};