322. 零钱兑换

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

        for (int i = 0; i < coins.size(); i++)
        {
            if (coins[i] < dp.size())
                dp[coins[i]] = 1;
        }

        for (int i = 1; i <= amount; i++)
        {
            int mi = INT_MAX;
            for (int j = 0; j < coins.size(); j++)
            {
                if (i > coins[j] && dp[i - coins[j]] != -1)
                {
                    int num = min(dp[i - coins[j]] + 1, dp[i]!=-1? dp[i]:INT_MAX);
                    if (mi > num)
                    {
                        mi = num;
                    }
                }
            }

            if (mi != INT_MAX)
            {
                dp[i] = min(dp[i] != -1 ? dp[i] : INT_MAX, mi);
            }
        }

        return dp[amount];
    }
};