动态规划经典模型：0-1 背包与最长公共子序列

2.2. DP 分析与求解 (二维数组)

步骤 1: 状态定义

问题的限制条件有两个：可供选择的物品范围和背包的剩余容量。为了唯一确定一个子问题的解，我们的状态定义必须包含这两个维度。

dp[i][j]：一个精确的、无歧义的定义是：在从前 i 个物品（即物品 0到物品 i-1）中进行选择时，对于一个容量为 j 的背包，所能获得的最大总价值。

• i 的范围：0 到 n (物品数量)
• j 的范围：0 到 W (背包容量)
• dp 数组大小为 (n+1) x (W+1)，dp[0][...] 和 dp[...][0] 作为边界，简化了逻辑。

步骤 2: 状态转移方程

考虑 dp[i][j] 的值如何计算。这等价于思考对于第 i-1 号物品（因为 dp[i] 对应前 i 个物品），我们有什么选择：

1. 不放入第 i-1 号物品：
   • 决策：我们决定不将这个物品放入背包。
   • 结果：问题转化为：从前 i-1 个物品中选择，放入容量为 j 的背包，所能获得的最大价值。根据我们的状态定义，这正是 dp[i-1][j]。
2. 放入第 i-1 号物品：
   • 前提：当前背包容量 j 必须大于或等于第 i-1 号物品的重量 weights[i-1]。
   • 决策：我们决定将这个物品放入背包。
   • 结果：放入后，我们获得了 values[i-1] 的价值，但背包的可用容量减少了 weights[i-1]。剩余的容量 j - weights[i-1] 需要用来从前 i-1 个物品中选择，以获得最大价值。这个价值就是 dp[i-1][j - weights[i-1]]。因此，此决策的总价值为 dp[i-1][j - weights[i-1]] + values[i-1]。

为了获得最大价值，我们在这两种决策中取最优者。于是，状态转移方程诞生了：

// 如果当前背包容量 j 不足以放下第 i-1 号物品
if (j < weights[i-1]) {
    dp[i][j] = dp[i-1][j]; // 只能选择不放
} else {
    // 否则，在'不放'和'放'之间选择更优的
    dp[i][j] = std::max(
        dp[i-1][j], // 不放第 i-1 号物品
        dp[i-1][j - weights[i-1]] + values[i-1] // 放第 i-1 号物品
    );
}

步骤 3: 初始化

• dp[0][j] for j from 0 to W: 表示从前 0 个物品（即没有物品）中选择，无论背包容量多大，最大价值都是 0。
• dp[i][0] for i from 0 to n: 表示背包容量为 0，无论有多少物品可选，都无法装入，最大价值是 0。
• 当 dp 数组用 std::vector<std::vector<int>>(n + 1, std::vector<int>(W + 1, 0)) 创建时，这些初始值已自动设定为 0，无需额外处理。

步骤 4: 遍历顺序

观察状态转移方程，dp[i][j] 依赖于 dp[i-1] 行的数值。因此，我们必须先计算完第 i-1 行，才能计算第 i 行。这决定了我们的遍历顺序是：外层循环遍历物品 i（从 1 到 n），内层循环遍历背包容量 j（从 1 到 W）。

步骤 5: 返回结果

根据定义，dp[n][W] 代表从前 n 个物品中选择，放入容量为 W 的背包中的最大价值，这正是我们要求的最终解。

C++ 实现模板 (二维数组)

#include <vector>
#include <algorithm>

/**
 * @brief 使用动态规划解决 0-1 背包问题（二维 DP 数组实现）。
 * @param weights 包含 n 个物品重量的向量，下标从 0 开始。
 * @param values 包含 n 个物品价值的向量，下标从 0 开始。
 * @param capacity 背包的总容量 (W)。
 * @return int 可以获得的最大总价值。
 */
int zeroOneKnapsack_2D(const std::vector<int>& weights,
                       const std::vector<int>& values,
                       int capacity) {
    int n = weights.size();
    if (n == 0 || capacity <= 0) {
        return 0;
    }
    // dp[i][j]: 从前 i 个物品中选择，放入容量为 j 的背包的最大价值。
    // 尺寸为 (n+1) x (capacity+1) 以便处理边界。
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(capacity + 1, 0));

    // 外层遍历物品 (i 从 1 到 n)
    for (int i = 1; i <= n; ++i) {
        // 内层遍历背包容量 (j 从 1 到 capacity)
        for (int j = 1; j <= capacity; ++j) {
            // 注意：第 i 个物品的索引是 i-1
            int current_weight = weights[i - 1];
            int current_value = values[i - 1];
            if (j < current_weight) {
                // 容量不足，无法装入当前物品
                dp[i][j] = dp[i - 1][j];
            } else {
                // 在'不装入'和'装入'两种决策中取最大值
                dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - current_weight] + current_value);
            }
        }
    }
    return dp[n][capacity];
}

• 时间复杂度: O(n * W)，因为我们需要填充一个 n x W 大小的表格。
• 空间复杂度: O(n * W)，因为我们使用了一个二维 dp 数组。

2.3. 空间优化 (滚动数组/一维数组)

仔细观察状态转移方程 dp[i][j] = max(dp[i-1][j], dp[i-1][j - w] + v)，我们发现计算第 i 行的状态只依赖于第 i-1 行。这意味着之前的所有行 (i-2, i-3, …) 都是不必要的。这启发我们可以用一个一维数组来优化空间。

• 新的状态定义: dp[j] 表示容量为 j 的背包所能承载的最大价值。这个定义是'滚动'的，在遍历第 i 个物品时，它存储的是考虑了前 i-1 个物品的结果。
• 状态转移与遍历顺序的关键
  dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
  这里 dp[j] (等号左边) 是我们要计算的、考虑了物品 i 之后的状态。等号右边的 dp[j] 是未考虑物品 i 时的状态，而 dp[j - weights[i]] 也必须是未考虑物品 i 时的状态。为了保证这一点，内层循环必须逆序遍历容量 j（从 capacity 到 weights[i]）。
  • 为什么必须逆序？ 假设我们正序遍历。当计算 dp[j] 时，我们需要 dp[j - weights[i]] 的旧值（i-1 轮的值）。但如果正序，dp[j - weights[i]] 在计算 dp[j] 之前就已经被更新为本轮（i 轮）的值了。这意味着在同一轮物品 i 的计算中，我们可能多次使用了物品 i 的价值，这就把问题变成了完全背包问题。
  • 逆序的好处：当计算 dp[j] 时，dp[j - weights[i]] 尚未被本轮更新，它仍然保留着上一轮（i-1 轮）的状态。这完美地模拟了二维 dp 数组中 dp[i-1][...] 的效果。

C++ 实现模板 (一维数组)

/**
 * @brief 使用动态规划解决 0-1 背包问题（空间优化后的一维 DP 数组）。
 * @param weights ...
 * @param values ...
 * @param capacity ...
 * @return int 最大总价值。
 */
int zeroOneKnapsack_1D(const std::vector<int>& weights,
                       const std::vector<int>& values,
                       int capacity) {
    int n = weights.size();
    if (n == 0 || capacity <= 0) {
        return 0;
    }
    // dp[j]: 容量为 j 的背包能获得的最大价值。
    std::vector<int> dp(capacity + 1, 0);

    // 外层遍历物品
    for (int i = 0; i < n; ++i) {
        // 内层逆序遍历背包容量
        for (int j = capacity; j >= weights[i]; --j) {
            dp[j] = std::max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

• 时间复杂度: O(n * W)，没有变化。
• 空间复杂度: O(W)，显著优化。

第三章：经典模型二：最长公共子序列 (LCS)

3.1. 问题描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列 (Longest Common Subsequence) 的长度。

子序列：从原字符串中删除零个或多个字符，而不改变其余字符的相对顺序得到的新字符串。（例如，'ace' 是 'abcde' 的子序列）。
公共子序列：两个字符串所共有的子序列。

3.2. DP 分析与求解

步骤 1: 状态定义

LCS 问题涉及比较两个字符串的子问题。一个自然的子问题是比较两个字符串的前缀。

dp[i][j]：表示 text1 的前 i 个字符（即子串 text1[0...i-1]）与 text2 的前 j 个字符（即子串 text2[0...j-1]）的最长公共子序列的长度。

• i 的范围：0 to m (text1 的长度)
• j 的范围：0 to n (text2 的长度)
• dp 数组大小为 (m+1) x (n+1)。

步骤 2: 状态转移方程

我们考虑 dp[i][j] 如何从其子问题推导而来。关键在于比较 text1[i-1] 和 text2[j-1] 这两个字符：

1. 如果 text1[i-1] == text2[j-1]:
   • 发现：我们找到了一个新的公共字符。这个字符可以被添加到 text1[0...i-2] 和 text2[0...j-2] 的 LCS 的末尾，从而形成一个新的、更长的 LCS。
   • 推论：因此，text1[0...i-1] 和 text2[0...j-1] 的 LCS 长度，就是 text1[0...i-2] 和 text2[0...j-2] 的 LCS 长度加一。
   • 方程：dp[i][j] = dp[i-1][j-1] + 1
2. 如果 text1[i-1] != text2[j-1]:
   • 发现：这两个末尾字符不匹配，它们不能同时成为 LCS 的一部分。
   • 推论：那么，最长的公共子序列必须在以下两种情况中产生：
     • text1 的前 i-1 个字符 (text1[0...i-2]) 与 text2 的前 j 个字符 (text2[0...j-1]) 的 LCS。其长度为 dp[i-1][j]。
     • text1 的前 i 个字符 (text1[0...i-1]) 与 text2 的前 j-1 个字符 (text2[0...j-2]) 的 LCS。其长度为 dp[i][j-1]。
   • 方程：dp[i][j] 应取这两者中的较大值，即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

步骤 3 & 4: 初始化与遍历顺序

• 初始化: dp[0][j] 和 dp[i][0] 均表示一个空串与另一个字符串的 LCS，长度显然为 0。同样，使用 std::vector 的默认初始化即可。
• 遍历顺序: dp[i][j] 依赖于其左方 dp[i][j-1]、上方 dp[i-1][j] 和左上方 dp[i-1][j-1] 的值。因此，从上到下、从左到右填充 dp 数组是唯一的正确顺序。

步骤 5: 返回结果

最终解是比较完整的 text1 (长度 m) 和 text2 (长度 n)，即 dp[m][n]。

C++ 实现模板

#include <string>
#include <vector>
#include <algorithm>

/**
 * @brief 计算两个字符串的最长公共子序列 (LCS) 的长度。
 * @param text1 第一个字符串。
 * @param text2 第二个字符串。
 * @return int LCS 的长度。
 */
int longestCommonSubsequence(const std::string& text1,
                             const std::string& text2) {
    int m = text1.length();
    int n = text2.length();
    // dp[i][j]: text1 的前 i 个字符和 text2 的前 j 个字符的 LCS 长度。
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            // 字符串索引是 i-1 和 j-1
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

• 时间复杂度: O(m * n)。
• 空间复杂度: O(m * n)。 (同样可以优化到 O(min(m, n))，但会增加实现的复杂性，此处不展开)。

3.3. 拓展：重构 LCS 字符串

通常我们不仅想知道长度，还想得到具体的 LCS 字符串。这可以通过回溯 dp 数组来实现。

从 dp[m][n] 开始，我们反向推导路径：

• 如果 text1[i-1] == text2[j-1]，说明这个字符是 LCS 的一部分。我们将其加入结果，并移动到 dp[i-1][j-1]。
• 如果 text1[i-1] != text2[j-1]，我们比较 dp[i-1][j] 和 dp[i][j-1]，移动到值较大的那个格子，这代表了 LCS 的来源方向。
• 如此反复，直到 i 或 j 为 0。

// 伪代码
string lcs_string;
i = m, j = n;
while(i > 0 && j > 0) {
    if(text1[i-1] == text2[j-1]) {
        lcs_string += text1[i-1];
        i--;
        j--;
    } else if(dp[i-1][j] > dp[i][j-1]) {
        i--;
    } else {
        j--;
    }
}
reverse(lcs_string.begin(), lcs_string.end());

第四章：结论与展望

通过对 0-1 背包和最长公共子序列这两个经典模型的深度剖析，我们反复实践了动态规划的五步法。这套方法论是解决 DP 问题的通用钥匙。

• 核心在于抽象：将实际问题转化为状态和状态转移的数学模型。
• 状态定义是基石：一个好的状态定义能让状态转移方程的推导水到渠成。
• 可视化是利器：在纸上画出 dp 表格并手动填充几个值，能极大地帮助理解状态转移的过程。
• 优化是进阶：在掌握基本解法后，思考状态依赖关系，从而进行空间优化，是衡量开发者能力的重要标准。

动态规划的世界远不止于此，还包括区间 DP、树形 DP、状态压缩 DP 等更高级的模型。但万变不离其宗，掌握了本文所阐述的核心思想和分析方法，就拥有了探索更广阔 DP 世界的坚实基础。