LeetCode 322. Coin Change 动态规划

Coin Change
给定一组硬币和一个目标金额，返回最少用几个硬币能凑出目标金额，如果不能返回-1。

数组dp用来记录能凑出从 1 到 amount最少的硬币数量

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.size(); j++) {
                if (coins[j] <= i) {
                    // +1 硬币数量加一
                    dp[i] = min(dp[i - coins[j]] + 1, dp[i]);
                }
            }
        }
        return dp.back() > amount ? -1 : dp.back();
    }
};