/*
 * @lc app=leetcode.cn id=322 lang=cpp
 *
 * [322] 零钱兑换
 */

// @lc code=start
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0) return 0;
        vector<int> res(amount + 1, amount + 1);
        res[0] = 0;
        for (int i = 1; i < amount + 1; i++) {
            for (int coin : coins) {
                if (i < coin) continue;
                res[i] = min(res[i], res[i - coin] + 1);
            }
        }
        return res[amount] == (amount + 1) ? -1 : res[amount];
    }
};
// @lc code=end