# 322. Coin Change

### Idea

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

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

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

經過以上思考後寫出第一個跑得過的解<br/>
時間複雜度為 O( amount 大小 \* coins 長度)<br/>
空間複雜度為 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

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

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`