# **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://www.youtube.com/watch?v=H9bfqozjoqs
Provided by. NeetCode
###### tags: `dynamic programming` `medium` `leetcode` `值得再想`
Sign in with Wallet
Connect another wallet