322. 零钱兑换

 1 class Solution 
 2 {
 3 public:
 4     int coinChange(vector<int>& coins, int amount) 
 5     {
 6         vector<long long> dp(amount + 1,INT_MAX);
 7         dp[0] = 0;//总金额为0元所需的最少的硬币个数为0个
 8         for(int i = 0;i < coins.size();i ++)
 9         {
10             for(int j = coins[i];j <= amount;j ++)
11             {
12                 dp[j] = min(dp[j],dp[j - coins[i]] + 1);
13             }
14         }
15         return dp[amount] == INT_MAX ? -1 : dp[amount];
16     }
17 };