1. class Solution {
    2.     vector<int>count;
    3.     int dp(vector<int>& coins, int rem) {
    4.         if (rem < 0) return -1;
    5.         if (rem == 0) return 0;
    6.         if (count[rem - 1] != 0) return count[rem - 1];
    7.         int Min = INT_MAX;
    8.         for (int coin:coins) {
    9.             int res = dp(coins, rem - coin);
    10.             if (res >= 0 && res < Min) {
    11.                 Min = res + 1;
    12.             }
    13.         }
    14.         count[rem - 1] = Min == INT_MAX ? -1 : Min;
    15.         return count[rem - 1];
    16.     }
    17. public:
    18.     int coinChange(vector<int>& coins, int amount) {
    19.         if (amount < 1) return 0;
    20.         count.resize(amount);
    21.         return dp(coins, amount);
    22.     }
    23. };
    1. class Solution {
    2. public:
    3.     int coinChange(vector<int>& coins, int amount) {
    4.         int Max = amount + 1;
    5.         vector<int> dp(amount + 1, Max);
    6.         dp[0] = 0;
    7.         for (int i = 1; i <= amount; ++i) {
    8.             for (int j = 0; j < (int)coins.size(); ++j) {
    9.                 if (coins[j] <= i) {
    10.                     dp[i] = min(dp[i], dp[i - coins[j]] + 1);
    11.                 }
    12.             }
    13.         }
    14.         return dp[amount] > amount ? -1 : dp[amount];
    15.     }
    16. };
    18. 作者：LeetCode-Solution
    19. 链接：https://leetcode-cn.com/problems/coin-change/solution/322-ling-qian-dui-huan-by-leetcode-solution/
    20. 来源：力扣（LeetCode）
    21. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。