# 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的硬幣，
求組合的加總為amount的最小所需硬幣數。

### 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)
> **需考慮每個組合**，Greedy法 not work !


### Resource
[YT-Coin Change - Dynamic Programming Bottom Up - Leetcode 322](https://youtu.be/H9bfqozjoqs)
#### Result

#### Level:`Medium`