###### tags: `Leetcode` `medium` `dynamic programming` `python` `c++` `Top 100 Liked Questions`

# 322. Coin Change

## [解題想法:] 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.

**Example 1:**

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

**Example 2:**

Input: coins = [2], amount = 3
Output: -1

**Example 3:**

Input: coins = [1], amount = 0
Output: 0

## 解題想法:
* 此題為，給一數組表示硬幣總類，求最少的數量構成amount

* 使用DP:
* 定義dp[i]表示組成i元需要最少的硬幣數
* dp[i]=min(dp[i], dp[i-val]+1) for val in coins if i>=val
* 初始dp[0]=0: 0元不需要任何硬幣組成
* 雙迴圈判斷:
* 第一圈: 從coins總類開始更新
* 第二圈:
* for i in range(curCoins, amount+1)
* 更新dp
* return dp[-1] if dp[-1]!=float('inf') else -1

## Python:

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        #dp[i]表示組成i元需要最少的硬幣數
        #dp[i]=min(dp[i],dp[i-val]+1) for val in coins if i>= val
        #dp[0]=0
        dp=[float('inf')]*(amount+1)
        dp[0]=0
        #從coin種類更新
        for cur_coin in coins:
            for i in range(cur_coin,amount+1):
                dp[i]=min(dp[i],dp[i-cur_coin]+1)
        return dp[amount] if dp[amount]!=float('inf') else -1

result = Solution()
ans = result.coinChange(coins = [1,2,5], amount = 11)
print(ans)

## Python: Sol2
* 使用 [39. Combination Sum](/W7B2e-02R7GECNxeVr0_vA) 概念
* 邏輯正確，但套用此題會TLE
* 因為遞迴求組合的完全資訊，太耗時

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount==0:
            return 0
        self.ans=float('inf')
        #coins.sort()
        self.dfs(coins,amount,[])
        return self.ans if self.ans!=float('inf') else -1
    def dfs(self,coins,amount,path):
        if amount==0:
            self.ans=min(self.ans,len(path))
            return 
        for val in coins:
            if val>amount:
                break
            if path and val<path[-1]:
                continue
            self.dfs(coins,amount-val,path+[val])

## C++:

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, amount+1);
        dp[0]=0;
        for (auto curCoin : coins){
            for (int i=curCoin; i<amount+1; i++)
                dp[i]=min(dp[i], dp[i-curCoin]+1);
        }
        return (dp[amount]==amount+1)? -1:dp[amount];
    }
};