322. Coin Change

Idea

因為目的是找到符合條件之總和所需的最小金幣數量
故決定用動態規劃來嘗試解決此問題

解題之前 先定義動態規劃的狀態和觀察狀態間的關聯性:

1. dp[sum] 代表金幣加總為 sum 時所需要的最小金幣數
2. 目標總和 amount 以下之可能發生的子總和 sum 完全是取決於金幣的種類而定

經過以上思考後寫出第一個跑得過的解
時間複雜度為 O( amount 大小 * coins 長度)
空間複雜度為 O( amount 大小)

function coinChange(coins, amount) {
  const dp = Array(amount + 1).fill(Infinity)
  dp[0] = 0
  for (let sum = 0; sum <= amount; sum++) {
    for (let coin of coins) {
      if (sum - coin >= 0) dp[sum] = Math.min(dp[sum], dp[sum - coin] + 1)
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount]
}

Refactor

後來思考了一下為何效能不佳
最外層迴圈真的有必要從 0 → amount 嗎?
其實只以某個基準 coin 的值 → amount 也是完全 ok 的吧
因此把迴圈的條件內外對調微調了一下
省下了不少無意義的回圈

function coinChange(coins, amount) {
  const dp = Array(amount + 1).fill(Infinity)
  dp[0] = 0
  for (let coin of coins) {
    for (let sum = coin; sum <= amount; sum++) {
      dp[sum] = Math.min(dp[sum], dp[sum - coin] + 1)
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount]
}

tags: Leetcode JavaScript