给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：

  1. 输入：coins = [1, 2, 5], amount = 11
  2. 输出：3
  3. 解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

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

解法一：回溯（超时）

function coinChange(coins: number[], amount: number): number {
  coins.sort((a, b) => a - b)
  let n = coins.length
  let min = Number.MAX_VALUE
  function recursion(total: number, idx: number, path: Array<number>) {
    if(total === amount) {
      min = Math.min(min, path.length)
      return
    }
    for (let i = idx; i < n; i++) {
      const coin = coins[i]
      if (total + coin > amount) {
        break
      }
      recursion(total + coin, i, path.concat(coin))
    }
  }
  recursion(0, 0, [])
  return min === Number.MAX_VALUE ? -1 : min
};

解法二：DP

function coinChange(coins: number[], amount: number): number {

  let dp = new Array(amount + 1).fill(Number.MAX_VALUE)
  dp[0] = 0
  for (let coin of coins) {
    for (let i = 0; i <= amount; i++) {
      if (i >= coin) {
        dp[i] = Math.min(dp[i], dp[i-coin] + 1)
      }
    }
  }
  return dp[amount] === Number.MAX_VALUE ? -1 : dp[amount]
};