《序列 DP：C++ 中的“最长”套路与编辑距离》

序列 DP 就像是“找茬”或“连连看”。

  • LIS：在一堆乱序的数字里找最长的顺子。

  • LCS：比较两个 DNA 序列，找出共同的基因片段。

  • 编辑距离：Word 文档的“修订模式”，计算改一个单词需要多少次键盘敲击。

模块一：最长递增子序列（LIS）

1. 思路讲解

定义dp[i]：以nums[i]结尾的最长递增子序列的长度。

对于每个i，我们需要查看它之前的所有j(0 <= j < i)。

如果nums[j] < nums[i]，说明nums[i]可以接在nums[j]后面形成一个新的递增序列。

状态转移：dp[i] = max(dp[i], dp[j] + 1)。

2. 代码详解

cpp

class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; vector<int> dp(n, 1); // 初始化为1，因为每个元素至少可以单独成一个序列 int ans = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j] + 1); } } ans = max(ans, dp[i]); // 更新全局最大值 } return ans; // 注意：返回的是ans，不是dp[n-1] } };

  • 易错点：答案不是dp.back()，因为最长的序列不一定以最后一个元素结尾。必须维护一个全局变量ans。

模块二：最长公共子序列（LCS）

1. 思路讲解

定义dp[i][j]：字符串text1的前i个字符和text2的前j个字符的最长公共子序列长度。

  • 情况 1：text1[i-1] == text2[j-1]（字符相同）。

    这两个字符一定在 LCS 中，所以dp[i][j] = dp[i-1][j-1] + 1。

  • 情况 2：text1[i-1] != text2[j-1]（字符不同）。

    这两个字符至少有一个不在 LCS 中。可能是删掉text1[i-1]，也可能是删掉text2[j-1]。

    所以dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

2. 代码详解

cpp

class Solution { public: int longestCommonSequence(string text1, string text2) { int m = text1.size(), n = text2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (text1[i - 1] == text2[j - 1]) { // 字符相同，两边都推进一格 dp[i][j] = dp[i - 1][j - 1] + 1; } else { // 字符不同，取删掉左边或删掉右边的较大值 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } };

  • C++ 字符串：text1[i-1]是因为 DP 数组从 1 开始计数，而 String 从 0 开始。

模块三：编辑距离（Levenshtein Distance）

1. 思路讲解

定义dp[i][j]：将word1的前i个字符转换成word2的前j个字符所需的最少操作数。

操作有三种：插入、删除、替换。

  • 插入：在word1插入一个字符，等价于word2减少一个字符：dp[i][j-1] + 1。

  • 删除：在word1删除一个字符：dp[i-1][j] + 1。

  • 替换：如果两个字符不同，替换最后一个字符：dp[i-1][j-1] + 1。

  • 特殊情况：如果word1[i-1] == word2[j-1]，无需操作，直接继承dp[i-1][j-1]。

2. 代码详解

cpp

class Solution { public: int minDistance(string word1, string word2) { int m = word1.size(), n = word2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 初始化：word1变成空串，只能靠删除；空串变成word2，只能靠插入 for (int i = 1; i <= m; i++) dp[i][0] = i; for (int j = 1; j <= n; j++) dp[0][j] = j; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1[i - 1] == word2[j - 1]) { // 字符相同，无需操作 dp[i][j] = dp[i - 1][j - 1]; } else { // 字符不同，取三种操作的最小值 + 1（本次操作成本） dp[i][j] = min({ dp[i - 1][j] + 1, // 删除 dp[i][j - 1] + 1, // 插入 dp[i - 1][j - 1] + 1 // 替换 }); } } } return dp[m][n]; } };

  • C++ 技巧：min({a, b, c})是 C++11 以后支持的初始化列表用法，可以一次性比较多个值。

总结：C++ DP 避坑指南

  1. 数组大小：为了逻辑清晰，通常开dp[n+1]或dp[m+1][n+1]，牺牲一点空间换取代码可读性。

  2. 初始化：

    • 求最大值时，初始化为0或INT_MIN。

    • 求最小值时，初始化为INT_MAX。

    • 布尔型初始化dp[0] = true。

  3. 遍历顺序：

    • 0-1 背包：容量倒序。

    • 完全背包：容量正序。

    • 序列 DP：通常是双重循环，注意内外层逻辑。

  4. 引用传参：在函数中传递大型vector时，务必使用const vector<int>&或vector<int>&，否则会复制整个数组，导致超时（TLE）。

谢谢