---
# System prepended metadata

title: '**Leetcode筆記(Coin Change)**'
tags: [值得再想, medium, dynamic programming, leetcode]

---

# **Leetcode筆記(Coin Change)**


:::info
:information_source: 題目 : Coin Change, 類型 : dynamic programming , 等級 : medium
日期 : 2023/02/24，2023/06/12，2023/07/19，2024/03/26，2024/10/25
:::


### 嘗試

想說用大的幣值下去算，一定會比較少coin，中間有用除法與餘數去得到它剩下的錢，但如果看[1,3,4,5]然後amount為7，用3,4會比用5,1,1好
```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        res = 0
        coins.sort()
        coinB = 12
        for i in reversed(range(len(coins))):
            if coinB < coins[i]:
                continue
            coinA = amount // coins[i] # amount / coins = coinA ...coinB
            res = res + coinA
            amount = amount - coinA * coins[i]
            coinB = amount % coins[i]
            if i == 0 and coinB != 0:
                return -1
            coinA = coinB
            
        return res
```
2023/06/12
永遠都是算"組成自己的最小次數(機會成本)"
而可以用的機會成本就是"不同coins的種類"

也是用dp陣列去想，先初始化一個dp[0]，並且更新每一個dp[]
找各種不同的coin去組合，如果有多個dp可選，那就取最小的

```python
dp[i] = min(dp[i - c] + 1, dp[i])

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float("inf")] * (amount + 1)
        dp[0] = 0

        # 要改dp
        for i in range(1, amount + 1):
            # 每種coin都試試看
            for c in coins:
                if i >= c:
                    # + 1 為dp[c]此硬幣本身的數量
                    dp[i] = min(dp[i - c] + 1, dp[i])

        if dp[amount] == float("inf"): 
            return -1
        else:
            return dp[amount]
```
2023/07/19
* 也用bottom up的想法，從 1 ~ amount 開始算，並把結果儲存在dp中
(這樣的好處是，假設有5這個數字存在，那dp[5]就可以用dp[3]和dp[2]或是dp[1]和dp[4]去想，不用每一次都dfs)
* 如果某一種amount不能用存在coin組成，它的**最小組成量必定是** (**某一個coin** + 剩下的數字)
* 如果某一種amount能用存在coin組成，dp[該amount] = 1，但不需要為了它去重新寫dp式子，因為1 + dp[a - c] = 1 + dp[0] = 1 + 0 = 1
```python
dp[a] = min(dp[a], 1 + dp[a - c])
```

    
```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float("inf")] * (amount + 1) # 一定要無限大 因為之後會比小
        dp[0] = 0 # amount為0 為0種組合

        for a in range(1, amount + 1):
            for c in coins:
                if a >= c:
                    dp[a] = min(dp[a], 1 + dp[a - c])
        
        if dp[amount] == float("inf"):
            return -1
        return dp[amount]
```

2024/03/26
如果沒有倒數兩行，會跑出return value不能是inf的錯誤
其實用上面那個解法，就可以同時內涵兩個if a = c時，dp[a] = 1的結果了
```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float("inf")] * (amount + 1)
        dp[0] = 0

        for a in range(amount + 1):
            for c in coins:
                if a == c:
                    dp[a] = 1
                    continue
                if a > c:
                    dp[a] = min(1 + dp[a - c], dp[a])
        
        if dp[amount] == float("inf"):
            return -1
        
        return dp[amount]
```

2024/10/25
```python
# amount = 3
# coins = [1, 2]

#     0, 1, 2, 3
# 1   0, 1, dp[0][j - c] = 2, dp[0][j - c]
# 2   0, 1, (dp[1][j - c], 2) 


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [[float("inf")] * (amount + 1) for _ in range(len(coins) + 1)] # (coins + 1) * (amount + 1)
        # initial for 0 amount
        for i in range(len(coins) + 1):
            dp[i][0] = 0

        for i in range(1, len(coins) + 1):
            for j in range(amount + 1):
                c = coins[i - 1]
                if c <= j:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - c] + 1)
                else:
                    dp[i][j] = dp[i - 1][j]
        
        return dp[len(coins)][amount] if dp[len(coins)][amount] != float("inf") else -1
```


---
### **優化**
DFS，backtracking
自己初始化0
dp[a] -> 執行行例如ex1.中coins = [1,2,5], amount = 11，若amount為2則會為1個2元的coin會花費最少硬幣
1 + dp[a - n] -> 若有coins=[1,3,4]然後有amount = 7就可以為1(coin=3)+dp[4](coin 4)
時間複雜度O(amount * coin)，空間複雜度O(amount)

```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount + 1] * (amount + 1) # 可以為任意值
        dp[0] = 0
        for a in range(1, amount + 1): # 算完amount以下的每個數字
            for n in coins:
                if a >= n:
                    dp[a] = min(dp[a], 1 + dp[a - n]) 
        if dp[amount] == amount + 1: # list沒變
            return -1
        else:
            return dp[amount]
```
---


**:warning: 錯誤語法** 
:::warning

:::


**:thumbsup:學習** 
:::success
denominations : 幣值

Tabulation: bottom up
從子問題的結果開始計算往上累算。
Memorization: top down
從原問題往下遞迴推算。

dp = [amount + 1] * (amount + 1) # 初始化長度

:::

**思路**
如果amount為7，就把7以下的函式(amonut)都算出來，在一個一個對
![](https://i.imgur.com/ypJDPbv.png)
![](https://hackmd.io/_uploads/ByAavHVP3.png)
![](https://hackmd.io/_uploads/By58hHNwn.png)


**講解連結**
https://www.youtube.com/watch?v=H9bfqozjoqs
Provided by. NeetCode

###### tags: `dynamic programming` `medium` `leetcode` `值得再想`