322.零钱兑换.md

322.零钱兑换

/*
 * @lc app=leetcode.cn id=322 lang=typescript
 *
 * [322] 零钱兑换
 */

// @lc code=start
function coinChange(coins: number[], amount: number): number {}
// @lc code=end

解法 1: 动态规划

• 时间复杂度:

• 空间复杂度:

• 状态: dp[i] 表示凑齐总金额为 i 最少需要的硬币数

• 递推方程: c in coins; dp[i]=min(dp[i],dp[i-c]) 其中 c 表示每种硬币的面额

function coinChange(coins: number[], amount: number): number {
  let dp: number[] = [0, ...new Array(amount).fill(Infinity)]
  for (let i = 1; i <= amount; i++) {
    for (const c of coins) {
      if (i >= c) dp[i] = Math.min(dp[i], dp[i - c] + 1)
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount]
}

解法 2: 外循环使用硬币面额

• 时间复杂度:
• 空间复杂度:

function coinChange(coins: number[], amount: number): number {
  const dp: number[] = [0, ...Array(amount).fill(Infinity)]
  for (const c of coins) {
    for (let i = c; i <= amount; i++) {
      dp[i] = Math.min(dp[i], dp[i - c] + 1)
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount]
}

• https://leetcode.com/problems/coin-change/discuss/77373/6-7-lines-2-ways

解法 3: 递归带缓存

• 时间复杂度:
• 空间复杂度:

function coinChange(coins: number[], amount: number): number {
  const cache: number[] = []
  const recursive = (coins: number[], amount: number): number => {
    if (amount < 0) return Infinity
    if (amount === 0) return 0

    if (cache[amount] !== undefined) return cache[amount]

    let min = Infinity
    for (const c of coins) {
      min = Math.min(min, recursive(coins, amount - c) + 1)
    }
    cache[amount] = min
    return cache[amount]
  }
  const res = recursive(coins, amount)
  return res === Infinity ? -1 : res
}

解法 4: 广度优先搜索带缓存

function coinChange(coins: number[], amount: number | number[], count = 1, cache = new Set()): number {
  if (!amount) return 0
  if (!Array.isArray(amount)) amount = [amount]
  if (!amount.length) return -1

  const nexts: number[] = []
  for (const cur of amount) {
    for (const coin of coins) {
      const next = cur - coin
      if (next === 0) return count
      if (next > 0 && !cache.has(next)) {
        cache.add(next)
        nexts.push(next)
      }
    }
  }
  return coinChange(coins, nexts, count + 1, cache)
}

Case

test.each([
  { input: { coins: [1, 2, 5], amount: 11 }, output: 3 },
  { input: { coins: [2], amount: 3 }, output: -1 },
  { input: { coins: [1], amount: 0 }, output: 0 },
  { input: { coins: [1], amount: 1 }, output: 1 },
  { input: { coins: [1], amount: 2 }, output: 2 },
  { input: { coins: [186, 419, 83, 408], amount: 6249 }, output: 20 },
])('input: coins = $input.coins, amount = $input.amount', ({ input: { coins, amount }, output }) => {
  expect(coinChange(coins, amount)).toBe(output)
})