322. 零钱兑换

https://leetcode-cn.com/problems/coin-change/

原题

给定不同面额的硬币 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] <= 231 - 1
0 <= amount <= 104

题目分析

这道题是典型的动态规划求最值的问题，求凑成总金额所需的最少的硬币个数。那碰到求最值的问题其实就是要穷举出所有满足条件的情况，那就需要看如何来穷举。
假设提供面值为 1、2、5，总金额为 11，那么枚举的过程如下：

我们可以看出求总金额为 11 的过程，可以分为求总金额为 10 + 1，总金额为 9 + 2，总金额为 6 + 5的过程。因此我们可以写出递归从上到下的算法为：

const coinChange = (coins, amount) => {
  if (amount === 0) return 0
  if (amount < 0) return -1
  let min = Number.MAX_SAFE_INTEGER
  for (let i = 0; i < coins.length; i++) {
    let sub = coinChange(coins, amount - coins[i])
    if (sub < 0) continue
    min = Math.min(min, sub + 1)
  }
  return min === Number.MAX_SAFE_INTEGER ? -1 : min
}

递归的时间复杂度为 子问题总数 x 每个子问题的时间。子问题总数为 o(n * k), 每个子问题有个 for 循环，复杂度为 o(k)。所以总的时间复杂度为 o(n * k * k)。

提交，提示超出时间限制。那么做一些优化。
我们可以看到在枚举的过程中，coinChange(9) 和 coinChange(5) 是重复计算的，所以我们可以把这些值存储下来，用到的时候先去查询看看之前是不是计算过，没有的话再去计算。

const coinChange = (coins, amount) => {
  let mem = []
  return dp(coins, amount, mem)
}
const dp = (coins, amount, mem) => {
  if (amount === 0) return 0
  if (amount < 0) return -1
  if (mem[amount]) return mem[amount]
  let min = Number.MAX_SAFE_INTEGER
  for (let i = 0; i < coins.length; i++) {
    const sub = dp(coins, amount - coins[i], mem)
    if (sub < 0) continue
    min = Math.min(min, sub + 1)
  }
  if (!mem[amount]) mem[amount] = min === Number.MAX_SAFE_INTEGER ? -1 : min
  return mem[amount]
}

通过。带存储的备忘录减小了子问题的数量，子问题的总数为 n，处理一个子问题的时间不变为 o(k)，所以总的时间复杂度为 o(n * k)。

那么我们是否可以先求出上面的 mem 数组，再去返回 mem[amount] 的值呢？当然是可以的，这就是动态规划从下到上的做法。

const coinChange = (coins, amount) => {
  const dp = new Array(amount + 1).fill(Number.MAX_SAFE_INTEGER)
  dp[0] = 0
  for (let i = 0; i < dp.length; i++) {
    for (let j = 0; j < coins.length; j++) {
      if (i - coins[j] < 0) continue
      dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)
    }
  }
  if (dp[amount] === Number.MAX_SAFE_INTEGER) return -1
  return dp[amount]
}