https://leetcode.com/problems/coin-change/
## タグ
## 概要
> You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money.
>
> Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return `-1`.
>
> You may assume that you have an infinite number of each kind of coin.
## 方針
### Intuition
大きい金額のcoinからgreedyに選んでいけば答えが求まるかなと思ったが違った。
例） `coins = [2, 3, 5], amount = 21`のとき
greedyに選ぶと5を4回使って残りの1に対応するcoinがないので払えなくなってしまう。
答えがcoinの枚数だけで枚数はいま注目しているamountより小さいamountに依存する性質があるのでDPで解けそう。
基本的なケースは `amount = 0`のときでこのときは0枚で良い。
それ以外の場合はたとえば`coins = [1, 2, 5]`のときはn-1, n-2, n-5のときの枚数にプラス1した枚数になる。
### Top Down DP
Time Complexity: $O(mn)$ ← それぞれの状態についてm回の操作が発生する
Space Complexity: $O(n)$ ← 合計額の状態は0からamountまでのn + 1個ある
Where: `m = len(coins), n = amount`
```python
def coinChange(self, coins: List[int], amount: int) -> int:
@cache
def dfs(amount: int) -> int:
if amount == 0:
return 0
minNum = inf
for coin in coins:
if amount >= coin:
prevStateNum = dfs(amount - coin)
minNum = min(minNum, prevStateNum + 1)
return minNum
minNum = dfs(amount)
return minNum if minNum != inf else -1
```
### Bottom Up DP
Time Complexity: $O(mn)$
Space Complexity: $O(n)$
Where: `m = len(coins), n = amount`
```python
def coinChange(self, coins: List[int], amount: int) -> int:
coinNums = [inf] * (amount + 1)
coinNums[0] = 0
for curAmount in range(amount + 1):
for coin in coins:
if curAmount >= coin:
coinNums[curAmount] = min(coinNums[curAmount], coinNums[curAmount - coin] + 1)
return coinNums[amount] if coinNums[amount] != inf else -1
```