[518] 零钱兑换 II

回溯

details

var change = function (amount, coins) {
    let ans = 0;
    backtrack(0, amount);
    function backtrack(sum, max) {
        if (sum === max) {
            ans++;
            return;
        }
        if (sum > max) {
            return;
        }
        for (const coin of coins) {
            backtrack(sum + coin, max);
        }
    }
    return ans;
};

如上代码没有考虑重复问题,导致结果不对

[1, 1, 1, 1], [1, 1, 1, 1];

var change = function (amount, coins) {
    let ans = 0;
    backtrack(0, amount, 0);

    function backtrack(sum, max, startIndex) {
        if (sum === max) {
            ans++;
            return;
        }
        if (sum > max) {
            return;
        }
        for (let i = startIndex; i < coins.length; i++) {
            backtrack(sum + coins[i], max, i);
        }
    }
    return ans;
};

记忆优化

var change = function (amount, coins) {
    let memo = new Map();
    return backtrack(0, amount, 0);

    function backtrack(sum, max, startIndex) {
        if (sum === max) {
            return 1;
        }
        if (sum > max) {
            return 0;
        }
        const key = `${sum}-${max}-${startIndex}`;
        if (memo.has(key)) return memo.get(key);

        let count = 0;
        for (let i = startIndex; i < coins.length; i++) {
            let result = backtrack(sum + coins[i], max, i);
            count += result;
        }
        memo.set(key, count);
        return count;
    }
};

动态规划

details

动态规划思路：

1. 定义状态：

   • 使用 dp[i] 表示金额为 i 时的组合总数。

2. 状态转移方程：

   • 对于每一种硬币 coin，更新 dp[i]，即从 dp[i - coin] 转移过来。
   • 具体公式为：dp[i] += dp[i - coin]，表示考虑当前硬币 coin 后，i 金额的组合方式等于不考虑 coin 时的组合方式加上减去 coin 面额后的组合方式。

3. 初始化：

   • 由于金额为 0 时的组合方式只有一种，即什么都不选，所以 dp[0] = 1。

4. 遍历顺序：

   • 遍历硬币数组，对于每个硬币，从金额 coin 遍历到 amount，更新每个 dp[i] 的值。

var change = function (amount, coins) {
    // 定义 dp 数组，dp[i] 表示凑成金额 i 的组合数
    let dp = new Array(amount + 1).fill(0);
    dp[0] = 1; // 凑成金额 0 有一种方法：不使用任何硬币

    // 遍历每个硬币
    for (let coin of coins) {
        // 对于每个硬币，从 coin 到 amount 更新 dp 数组
        for (let i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }

    return dp[amount];
};