零錢兌換問題（動态規劃）

采用動态規劃思想：dp[i] 表示總金額為 i 所需要的最少硬币數。

對于金額為i，周遊coins數組時，若coins[j]值若是大于總金額i，則說明該硬币無法用于兌換，若是小于等于總金額，則狀态轉移方程為：dp[i]=min(dp[i],dp[i-coins[j]]+1)； 即使用該枚硬币，那麼總數量就是 該枚硬币數 1 + 總金額減去該硬币值後剩餘金額所需要的最少硬币數。 即1+dp[ i-coins[ j ] ]

最後注意判斷dp[i]的值與amount的大小，若是大于，則說明無法兌換，傳回-1。

代碼如下：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n=coins.size();
        vector<int>dp(amount+1,amount+1); //初始化大小和數值都為amount+1的一維數組
        dp[0]=0; //總金額為0所需的硬币數為0
        if(n==0||amount==0) return 0;
        for(int i=1;i<=amount;i++)
        {
           for(int j=0;j<n;j++)
            {
                if(coins[j]<=i)  //隻有不大于總金額的硬币才能兌換
                    dp[i]=min(dp[i],dp[i-coins[j]]+1);
            } 
        }
        return dp[amount]>amount?-1:dp[amount];
    }
};