《序列 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 避坑指南
数组大小：为了逻辑清晰，通常开
dp[n+1]或dp[m+1][n+1]，牺牲一点空间换取代码可读性。初始化：
求最大值时，初始化为
0或INT_MIN。求最小值时，初始化为
INT_MAX。布尔型初始化
dp[0] = true。
遍历顺序：
0-1 背包：容量倒序。
完全背包：容量正序。
序列 DP：通常是双重循环，注意内外层逻辑。
引用传参：在函数中传递大型
vector时，务必使用const vector<int>&或vector<int>&，否则会复制整个数组，导致超时（TLE）。