力扣链接：322.零钱兑换

难度：⭐⭐

解题关键词：动态规划、背包问题

解题思路：dp[i]表示金额要到 i 需要最少多少个硬币，dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i])，coin[j]表示每一个硬币。

function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(amount + 1);

  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (let j = 0; j < coins.length; j++) {
      if (i - coins[j] >= 0) {
        dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]);
      }
    }
  }

  // 因为刚开始初始化为都比 amount 大，如果最后还是比 amount 大，代表没找到
  return dp[amount] > amount ? -1 : dp[amount];
}