背包问题与动态规划

从经典背包问题入手，彻底掌握动态规划的核心思维

前置知识：建议先理解递归和回溯的基本概念。动态规划本质上是回溯的"记忆化"升级版。

什么是动态规划

动态规划（Dynamic Programming，DP）是一种通过把复杂问题分解为更小的重叠子问题来求解的算法范式。它的核心思想是：记住已经求解过的子问题答案，避免重复计算。

一个问题能用 DP 求解，必须满足两个条件：

DP 有两种实现方式：自顶向下（记忆化搜索，递归 + 缓存）和自底向上（递推填表，迭代）。两者本质相同，只是计算顺序不同。

0-1 背包问题

问题描述：有 N 件物品和一个容量为 W 的背包。第 i 件物品的重量为 wt[i]，价值为 val[i]。每件物品只能选或不选（0 或 1），求能装入背包的最大总价值。

DP 思路

定义 dp[i][w] 表示：对于前 i 件物品，背包容量为 w 时能获得的最大价值。对于第 i 件物品，有两种选择：

取两者最大值即可。最终答案在 dp[N][W]。

function knapsack01(wt, val, W) {
    const N = wt.length;
    const dp = Array(N+1).fill(0).map(() => Array(W+1).fill(0));

    for (let i = 1; i <= N; i++) {
        for (let w = 0; w <= W; w++) {
            if (w < wt[i-1]) {
                dp[i][w] = dp[i-1][w];  // 装不下，不选
            } else {
                dp[i][w] = Math.max(
                    dp[i-1][w],                     // 不选
                    dp[i-1][w-wt[i-1]] + val[i-1]   // 选择
                );
            }
        }
    }
    return dp[N][W];
}

如果用二维表格来可视化，dp[i][w] 的值仅依赖于上一行 dp[i-1][...]。这个性质正是后面空间优化的基础。

完全背包问题

区别：每件物品可以选无限次，而非只能选一次。状态转移方程变为：

dp[i][w] = max(dp[i-1][w], dp[i][w-wt[i]] + val[i])

注意第二个参数是 dp[i][w-wt[i]]（当前行），而不是 dp[i-1][w-wt[i]]（上一行）。这意味着选择第 i 件物品后，仍然可以再选同一件物品。

function knapsackComplete(wt, val, W) {
    const N = wt.length;
    const dp = Array(W+1).fill(0);

    for (let i = 0; i < N; i++) {
        for (let w = wt[i]; w <= W; w++) {  // 正序遍历！
            dp[w] = Math.max(dp[w], dp[w-wt[i]] + val[i]);
        }
    }
    return dp[W];
}

注意这里使用了一维数组优化（见下文），且内层循环是正序遍历，这是完全背包与 0-1 背包的关键区别。

DP 解题五步法

面对任何 DP 问题，按以下五个步骤思考：

  1. 定义状态：明确 dp[i] 或 dp[i][j] 代表什么含义。这是最关键的一步，定义准确了后面水到渠成。
  2. 推导状态转移方程：找出当前状态和之前状态的关系。问自己：要得到当前最优解，可以从哪些子问题转移过来？
  3. 确定初始值：DP 表格的第一行/第一列（或 dp[0]）的值是什么？这些是递推的起点。
  4. 确定遍历顺序：正序还是倒序？外层循环是物品还是容量？顺序不同，结果可能完全错误。
  5. 返回结果：答案在 DP 表格的哪个位置？dp[n]？dp[n][W]？还是需要遍历取最大值？

经典例题：零钱兑换

问题：给定不同面额的硬币 coins 和一个总金额 amount，计算可以凑成总金额的最少硬币个数。如果无法凑出，返回 -1。

这是完全背包的变种——每枚硬币可以用无限次，"物品重量"是面额，"物品价值"统一为 1（每个硬币计 1 个数），目标是求恰好装满时的最小价值。

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

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

这里 dp[i] 表示凑出金额 i 所需的最少硬币数。dp[0] = 0 是边界条件——凑 0 元需要 0 个硬币。其余初始化为 Infinity 表示"暂时不可达"。

空间优化技巧

当 dp[i] 只依赖于 dp[i-1] 时，可以用滚动数组把二维压成一维，将空间复杂度从 O(NW) 降到 O(W)。

关键规则：

记忆口诀："零一倒着走，完全正着来"。

常见陷阱