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

序列 DP 就像是“找茬”或“连连看”。LIS在一堆乱序的数字里找最长的顺子。LCS比较两个 DNA 序列找出共同的基因片段。编辑距离Word 文档的“修订模式”计算改一个单词需要多少次键盘敲击。模块一最长递增子序列LIS1. 思路讲解定义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. 代码详解cppclass Solution { public: int lengthOfLIS(vectorint nums) { int n nums.size(); if (n 0) return 0; vectorint 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。模块二最长公共子序列LCS1. 思路讲解定义dp[i][j]字符串text1的前i个字符和text2的前j个字符的最长公共子序列长度。情况 1text1[i-1] text2[j-1]字符相同。这两个字符一定在 LCS 中所以dp[i][j] dp[i-1][j-1] 1。情况 2text1[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. 代码详解cppclass Solution { public: int longestCommonSequence(string text1, string text2) { int m text1.size(), n text2.size(); vectorvectorint dp(m 1, vectorint(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 Distance1. 思路讲解定义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. 代码详解cppclass Solution { public: int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorvectorint dp(m 1, vectorint(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})是 C11 以后支持的初始化列表用法可以一次性比较多个值。总结C DP 避坑指南数组大小为了逻辑清晰通常开dp[n1]或dp[m1][n1]牺牲一点空间换取代码可读性。初始化求最大值时初始化为0或INT_MIN。求最小值时初始化为INT_MAX。布尔型初始化dp[0] true。遍历顺序0-1 背包容量倒序。完全背包容量正序。序列 DP通常是双重循环注意内外层逻辑。引用传参在函数中传递大型vector时务必使用const vectorint或vectorint否则会复制整个数组导致超时TLE。谢谢