Skip to content

凑零钱问题

· 4 min

题目#

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

示例1

输入：coins = [1, 2, 5], amount = 11

输出：3

解释：11 = 5 + 5 + 1，一共 3 枚硬币

示例2

输入：coins = [2], amount = 3

输出：-1

解释：无法凑成 3。

解题思路

要凑出的金额为 amount，可以先随便选择一枚硬币 coin，现在问题就变了：amount - coin 会得到一个余额 amount2，问题就变成了凑出金额为 amount2 需要多硬币。

换句话说：最少硬币凑出amount的解依赖于若干个最少硬币凑 amount - coin 的结果中的最优的那一个。

🙋是否存在重叠子问题？

求解凑amount的过程中，会变成凑amount-coin的子问题，而凑amount-coin的子问题又会变成凑amount-coin-coin2的子问题. 这里可以使用一个一维数组来存储从1...amount的最优解。

状态转移方程

代码实现

  1. 表格法
/**
 * 凑零钱问题：计算凑出 amount 所需的最少硬币数
 * @param {number[]} coins - 可使用的不同面值硬币
 * @param {number} amount - 目标金额
 * @return {number} - 最少硬币数，若无法凑出则返回 -1
 */
function coinChange(coins, amount) {
  // 1. 初始化 dp 数组，这里用一个一维数组就够了
  // 数组的每一项表示要凑出当前项金额的最少硬币数
  const dp = new Array(amount + 1).fill(Infinity)


  // 2. 初始条件
  // 凑出总金额0所需的硬币也是0
  dp[0] = 0


  // 外层循环表示从 1....amount 寻找最少硬币数
  // i 表示从 1....amount 的金额数
  for (i = 1; i <= amount; i++) {
    // 遍历所有面值的硬币
    for (const coin of coins) {
      // 当前硬币的面值不超过当前的 i
      if (i - coin >= 0 && dp[i - coin] !== Infinity) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1)
      }
    }
  }


  return dp[amount] === Infinity ? -1 : dp[amount]
}
  1. 记忆化搜索
/**
 * 凑零钱问题：计算凑出 amount 所需的最少硬币数
 * @param {number[]} coins - 可使用的不同面值硬币
 * @param {number} amount - 目标金额
 * @return {number} - 最少硬币数，若无法凑出则返回 -1
 */
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity)


  function helper(amount) {
    if (amount === 0) return 0
    if (amount < 0) return -1
    if (dp[amount] !== Infinity) return dp[amount]


    let minCoins = dp[amount]
    // 尝试每一种硬币
    for (const coin of coins) {
      const subResult = helper(amount - coin)


      if (subResult >= 0 && subResult < minCoins) {
        minCoins = subResult + 1
      }
    }
    dp[amount] = minCoins === Infinity ? -1 : minCoins
    return dp[amount]
  }


  return helper(amount)
}

-EOF-