給你一個(gè)整數(shù)數(shù)組?coins?，表示不同面額的硬幣；以及一個(gè)整數(shù)?amount?，表示總金額。

計(jì)算并返回可以湊成總金額所需的?最少的硬幣個(gè)數(shù)?。如果沒(méi)有任何一種硬幣組合能組成總金額，返回?-1?。

你可以認(rèn)為每種硬幣的數(shù)量是無(wú)限的。

示例?1：

輸入：coins = [1, 2, 5], amount = 11
輸出：3 
解釋：11 = 5 + 5 + 1

示例 2：

輸入：coins = [2], amount = 3
輸出：-1

示例 3：

輸入：coins = [1], amount = 0
輸出：0

思路

? ? ? ? 動(dòng)態(tài)規(guī)劃

代碼

class Solution {
public:int coinChange(vector<int>& coins, int amount) {if(amount == 0)return 0;vector<int> dp(amount+1, INT_MAX-1);int save;dp[0] = 0;for(int i=0; i<=amount; ++i){for(int j=0; j<coins.size(); ++j){save = i-coins[j];if(save >= 0)dp[i] = min(dp[save]+1, dp[i]);}}if(dp[amount] == INT_MAX-1)return -1;return dp[amount];}
};