# Leetcode 322. Coin Change
###### tags: `dp`
問題描述：
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.

想法：
這屬於比較基本的DP問題。利用總額度當做不斷改變的"狀態"，並藉由"選擇"不同面額的零錢來最小化所需的零錢數量，最後輸出最小結果。

其他細節：
base case => 面額為0，方法數是0

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,amount+1); //陣列數值初始化為 amount+1，有利於取最小值
        dp[0]=0;
        for (int j=0;j<amount+1;j++){
            for (auto i:coins){
                if (i>j) continue; //當面額比較大時，自然不需繼續
                dp[j]=min(dp[j],dp[j-i]+1); //找最佳解
            }
        }

        if (dp[amount]==amount+1) return -1;
        return dp[amount];

    }
};

類似題:
https://app.codingbar.ai/student/course/c27f1d2a-059c-4489-b152-1aef01a372d0-1671278551052/lesson/6cc98240-113f-11ec-a2c0-795109a86646/exercise/9603fb6b-6b79-4e76-8fed-7040bb097acc