动态规划，算一下$需要的最少硬币是多少

    1. class Solution {
    2. public:
    3.     int coinChange(vector<int>& coins, int amount) {
    4.         vector<int> dp(amount + 1, 1000000);
    5.         dp[0] = 0;
    6.         for(int i = 1; i <= amount; i++)
    7.         {
    8.             for(auto x: coins)
    9.             {
    10.                 if(i - x >= 0 && dp[i - x] != 1000000)
    11.                     dp[i] = min(dp[i], dp[i - x] + 1); 
    12.             }
    13.         }
    14.         if(dp[amount] == 1000000) return -1;
    15.         else return dp[amount];
    16.     }
    17. };

    第二次写题

    1. class Solution {
    2. public:
    3.     int coinChange(vector<int>& coins, int amount) {
    4.         vector<int> aCoins(amount + 1, 10000);
    5.         aCoins[0] = 0;
    6.         sort(coins.begin(), coins.end());
    7.         for(int i = 1; i <= amount; i++)
    8.         {
    9.             for(int k = 0; k < coins.size(); k++)
    10.             {
    11.                 if(i < coins[k]) break;
    12.                 if(aCoins[i - coins[k]] == 10000) continue;
    13.                 aCoins[i] = min(aCoins[i], aCoins[i - coins[k]] + 1);
    14.             }
    15.         }
    16.         return aCoins[amount] == 10000? -1:aCoins[amount];
    17.     }
    18. };