322.零钱兑换

题目：https://leetcode.cn/problems/coin-change

思路

经典的多重背包问题，只要把其中一处 i-1 改为 i 即可

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        auto dfs = [&](this auto&& dfs, int i, int c) -> int {

            if (i < 0) {
                return c == 0 ? 0 : INT_MAX / 2;
            }

            if (c < coins[i]) {
                return dfs(i - 1, c);
            }
            return min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1);
        };
        int res = dfs(n - 1, amount);
        return res == INT_MAX / 2 ? -1 : res;
    }
};

回溯加记忆化搜索

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

        auto dfs = [&](this auto&& dfs, int i, int c) -> int {

            if (i < 0) {
                return c == 0 ? 0 : INT_MAX / 2;
            }

            int& res = memo[i][c];
            if (res != -1) {
                return res;
            }

            if (c < coins[i]) {
                return res = dfs(i - 1, c);
            }
            return res = min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1);
        };
        int res = dfs(n - 1, amount);
        return res == INT_MAX / 2 ? -1 : res;
    }
};

回溯改递推

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector f(n + 1, vector<int>(amount + 1, INT_MAX / 2));
        f[0][0] = 0;

        for (int i = 0; i < n; i++) {
            for (int c = 0; c <= amount; c++) {
                if (c < coins[i]) {
                    f[i + 1][c] = f[i][c];
                } else {
                    f[i + 1][c] = min(f[i][c], f[i + 1][c - coins[i]] + 1);
                }
            }
        }
        int res = f[n][amount];
        return res == INT_MAX / 2 ? -1 : res;
    }
};

改为滚动数组

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector f(2, vector<int>(amount + 1, INT_MAX / 2));
        f[0][0] = 0;

        for (int i = 0; i < n; i++) {
            for (int c = 0; c <= amount; c++) {
                if (c < coins[i]) {
                    f[(i + 1) % 2][c] = f[i % 2][c];
                } else {
                    f[(i + 1) % 2][c] = min(f[i % 2][c], f[(i + 1) % 2][c - coins[i]] + 1);
                }
            }
        }
        int res = f[n % 2][amount];
        return res == INT_MAX / 2 ? -1 : res;
    }
};