322-零钱兑换 ​

function coinChange(coins: number[], amount: number): number {
  // 边界条件
  if (!amount) return 0

  // amount 为 0 时，不能由硬币组成，最少硬币个数为 0
  // 所以 dp[0] 是一个特殊情况，dp 长度为 amount + 1
  // Infinity 是一个特殊的占位符
  const dp = Array(amount + 1).fill(Number.POSITIVE_INFINITY)
  // 当所需面值和硬币面值相同时，会用到 dp[0]
  dp[0] = 0

  // 每一种硬币
  for (let i = 0; i < coins.length; i++) {
    // 硬币面值比 j 大时，不符合，只能是 0，没有修改必要
    // 硬币面值 <= j <= amount
    for (let j = coins[i]; j <= amount; j++) {
      // dp[j - coins[i]] + 1 当前循环时的解
      // dp[j] 之前的解
      // 两者取小值，为当前最优解 (局部最优解)，循环结束时的结果为全局最优解
      dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j])
      // console.log(`i => ${i} | j => ${j} | dp => ${dp}`)
    }
  }

  // 如果有符合的解，占位符会被替换为最少硬币个数
  return dp[amount] === Number.POSITIVE_INFINITY ? -1 : dp[amount]
}

function coinChange(coins: number[], amount: number): number {
  // 边界条件
  if (!amount) return 0

  // amount 为 0 时，不能由硬币组成，最少硬币个数为 0
  // 所以 dp[0] 是一个特殊情况，dp 长度为 amount + 1
  // Infinity 是一个特殊的占位符
  const dp = Array(amount + 1).fill(Number.POSITIVE_INFINITY)
  // 当所需面值和硬币面值相同时，会用到 dp[0]
  dp[0] = 0

  // 每一种硬币
  for (let i = 0; i < coins.length; i++) {
    // 硬币面值比 j 大时，不符合，只能是 0，没有修改必要
    // 硬币面值 <= j <= amount
    for (let j = coins[i]; j <= amount; j++) {
      // dp[j - coins[i]] + 1 当前循环时的解
      // dp[j] 之前的解
      // 两者取小值，为当前最优解 (局部最优解)，循环结束时的结果为全局最优解
      dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j])
      // console.log(`i => ${i} | j => ${j} | dp => ${dp}`)
    }
  }

  // 如果有符合的解，占位符会被替换为最少硬币个数
  return dp[amount] === Number.POSITIVE_INFINITY ? -1 : dp[amount]
}