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的最优解。

状态转移方程

  • 初始条件

    • dp[0]=0，凑的金额总额为0，不需要硬币，所以值也为0
    • dp[1...amount] 表示凑出从总金额为 1 到 amount 的最优解，一开始可以初始化为 Infinity

  • 状态转移方程

    dp[i]=min⁡coin∈coins(dp[i−coin]+1)dp[i] = \min_{\text{coin} \in \text{coins}} \bigl(dp[i - \text{coin}] + 1\bigr)

    首先是硬币集合：

    coin∈coins\text{coin} \in \text{coins}

    coin 是一个变量，coins 是一个集合，每次从 coins 里面去取值。coins =[1, 2, 5]，coin 第一次为 1，第二次为 2， 第三次为 5.

    接下来是：

    min⁡(...)\min\bigl(...)

    取最小值的意思。

    重点是括号里面的方程：

    (dp[i−coin]+1)\bigl(dp[i - \text{coin}] + 1\bigr)

    对于每一种硬币 coin，如果我选择了它，那么问题就变成了凑 dp[i - coin] 金额最少需要多少个硬币，得到其最优解之后，需要加上这一枚硬币本身。

代码实现

  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-