最长公共子序列
进阶LCS 用二维 DP 表记录两个字符串的最长匹配前缀。
// 算法讲解
最长公共子序列
与反转后的序列求 LCS，观察 DP 表填充过程。
待机
速度 中
待机 ⌨1int lcs(string s1, string s2) {
2 int m = s1.size(), n = s2.size();
3 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
4 for (int i = 1; i <= m; i++)
5 for (int j = 1; j <= n; j++) {
6 if (s1[i-1] == s2[j-1])
7 dp[i][j] = dp[i-1][j-1] + 1;
8 else
9 dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
10 }
11 return dp[m][n];
12}
复杂度分析
时间 O(mn)
空间 O(mn)
最优 O(mn)
最坏 O(mn)
算法讲解
最长公共子序列（LCS）要求在两个序列中找到一个最长的、不要求连续但保持相对顺序的子序列。
DP 状态 dp[i][j] 表示 s1 前 i 个字符与 s2 前 j 个字符的 LCS 长度。
若 s1[i-1] == s2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
它广泛应用于 diff 工具、版本对比和生物信息学中的序列比对。