LC 322. Coin Change

https://leetcode.com/problems/coin-change/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();

        vector<int> f(amount + 1, INT_MAX);
        f[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < n; j++) {
                if (i - coins[j] >= 0 && (f[i - coins[j]] != INT_MAX)) {
                    f[i] = min(f[i], f[i - coins[j]] + 1);
                }
            }
        }

        return f[amount] == INT_MAX ? -1 : f[amount];
    }
};

當我們要確認換出 amount = i 的方法數量就會是嘗試將 i - coins[j] 並且看在這樣的情況下有多少種可能，我們將所有的 coins 的結果加總就會是 amount = i 的所有可能。