[!info] related notes 动态规划 背包 DP 零钱兑换

DP 模板：完全背包

识别信号

• 每个物品可以无限次使用
• 凑金额 / 凑容量 / 最少硬币 / 方案数

二维定义

dp[i][j] = 前 i 个物品中，容量不超过 j 时的最优值 / 方案数

最值型二维模板

for (let i = 1; i <= n; i++) {
    for (let j = 0; j <= m; j++) {
        dp[i][j] = dp[i - 1][j];
        if (j >= w[i - 1]) {
            dp[i][j] = Math.max(dp[i][j], dp[i][j - w[i - 1]] + v[i - 1]);
        }
    }
}

一维优化模板

for (let i = 0; i < n; i++) {
    for (let j = w[i]; j <= m; j++) {
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
    }
}

为什么正序

因为同一轮里允许继续使用当前物品，所以更新后的 dp[j - w[i]] 可以继续参与转移。

最小样例

硬币：[1, 2, 5]

目标金额：11

可以重复用 5，所以答案能来自 5 + 5 + 1。

常见变形

• 最小硬币数
• 方案数（零钱兑换 II）
• 是否可达