Skip to main content

零钱兑换

题目​

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

分析​

  1. 判断是哪种题目
  2. 确定是动态规划
    1. 明确 dp 数组是啥意思
    2. 确定 dp 的递推公式

dp[i] 指的是：amount 为 i 的时候，最少多少个硬币

dp[i] 的递推公式：dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i])

题解​

const coinChange = function (coins, amount) {
  // 1. 创建初始 dp 数组，因为后面要拿最小值，所以默认都赋最大值
  const dp = Array(amount + 1).fill(Infinity)
  // 2. 设置 dp 数组的第一个值，没有这个值，无法开展计算
  dp[0] = 0
  // 3. 对硬币进行遍历
  for(let i = 0; i < coins.length; i++>) {
    // 4. 对总数进行遍历，注意 j 的起始值，必须要大于 coins[i]，因为后面 dp[j - coins[i]] 时，index 不能小于 0
    for(let j = coins[i]; j <= amount; j++) {
      // 5. 需要拿到 amount = j - coins[i] 时候的最少硬币数量，然后 +1
      // 6. 在当前，和前一个amount的数量中选择最小的一个
      dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1)
    }
  }
  // 7. 被赋过值的就是不是 Infinity，因此还是 Infinity 的，返回 -1
  return dp[amount] === Infinity ? -1 : dp[amount]
}