[!info] related notes 算法面试题型 MOC 动态规划 背包 DP

零钱兑换

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

题意

给你若干硬币面值 coins，每种硬币都可以使用无限次。问凑成金额 amount 的最少硬币数；如果凑不出来，返回 -1。

硬币面值按题意为正整数，amount 为非负整数；本题求最少枚数，不是组合数量（见 零钱兑换 II）。

为什么是完全背包

• 每个硬币可以重复使用
• 目标是“凑出金额 amount”
• 求的是最小值

状态

dp[j] 表示凑出金额 j 所需的最少硬币数。

转移

对于每个硬币 coin：

dp[j] = min(dp[j], dp[j - coin] + 1)

为什么正序

因为当前硬币可以重复使用，所以当前轮更新过的 dp[j - coin] 可以继续参与后面的转移。

边界

• dp[0] = 0
• 其他位置初始化成 INF

样例

coins = [1, 2, 5], amount = 11

• 11 = 5 + 5 + 1
• 最少需要 3 枚

JavaScript

var coinChange = function(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for (const coin of coins) {
        for (let j = coin; j <= amount; j++) {
            dp[j] = Math.min(dp[j], dp[j - coin] + 1);
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
};

易错点

• 初始化不能全填 0，否则最小值模型会错
• 在“硬币外层、金额内层”的压缩写法中要正序；倒序会把每种硬币限制为最多使用一次
• amount = 0 返回 0；无法凑出的状态保持 Infinity