DAY 18
0

# Day 18: LeetCode 322. Coin Change

## Tag: follow JohnTing's Day 17

### Source:

https://leetcode.com/problems/coin-change/

### 1.題意:

coins = [1,2,5] 代表 面額為1,2,5的硬幣，

### 2.思路:

• 作法
• curValue:目前值 before reaching amount
• dp[curValue] = 所花硬幣數
• dp[amount] 即答案

### 3.程式碼:

``````class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [amount+1]*(amount+1)
dp[0] = 0
# max = amount(all consist of 1)+1
'''
ex: amount = 11 means 11's 1 if have coin 1
To set max surely, we can plus 1.
[12,...,12]

?: number of combination
dp[0] = 0
dp[1] = ?
dp[2] = ??
...
dp[amount] = ??...

Run by actual value
[1,2,5]
dp[1] = 1 # 1x(1)=1
dp[2] = dp[1]+1 or dp[2-2]+1 -- select minimum
1) 1+1 (2)
2) 2 (1) ... v
How to process no solution(return -1) ?
Ans: compare default value of dp and dp[amount]
'''

for i in range(1,amount+1):
#print(i)
for coin in coins:
if i-coin>=0:
#print("In.")
dp[i] = min(dp[i-coin]+1,dp[i])
return dp[amount] if dp[amount]!=(amount+1) else -1
``````

### Concept from @JohnTing

DP+DFS(Brute Force solution)

### Resource

YT-Coin Change - Dynamic Programming Bottom Up - Leetcode 322

FRIENDS30