题面
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 __ 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入： text1 = "abcde", text2 = "ace"
输出： 3
解释： 最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
输入： text1 = "abc", text2 = "abc" 输出： 3 解释： 最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入： text1 = "abc", text2 = "def" 输出： 0 解释： 两个字符串没有公共子序列，返回 0 。
提示：
1 <= text1.length, text2.length <= 1000text1和text2仅由小写英文字符组成。
分析
-
dp[i][j]表示以 0-i 且 0-j 的最长公共子序列长度 -
递推公式
- 如果
s1[i]==s1[j]，则dp[i][j] = dp[i - 1][j - 1] + 1 - 如果
s1[i]!=s1[j]，则dp[i][j]=max(dp[i-1][j],dp[i][j-1])
- 如果
-
代码实现
class Solution { public: int longestCommonSubsequence(string text1, string text2) { int n1 = text1.size(), n2 = text2.size(); vector<vector<int>> dp(n1 + 1, vector(n2 + 1, 0)); for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; 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[n1][n2]; } }; -
原代码使用了
(n1+1) * (n2+1)的二维 DP 数组，但实际上计算dp[i][j]时，只依赖于：dp[i-1][j-1]（左上角）dp[i-1][j]（正上方）dp[i][j-1]（正左方）
-
因此可以将二维数组优化为一维数组（空间复杂度
O(min(n1, n2))），核心技巧是：-
用一维数组保存上一行的结果
-
用临时变量记录左上角的值（避免被覆盖）
-
遍历方向保持不变，从左到右更新数组
-
-
代码实现
class Solution { public: int longestCommonSubsequence(string text1, string text2) { // 优先选择较短的字符串作为列维度，进一步节省空间 if (text1.size() < text2.size()) { swap(text1, text2); } int n1 = text1.size(), n2 = text2.size(); // 用一维数组替代二维数组，空间复杂度从O(n1*n2)降到O(n2) vector<int> dp(n2 + 1, 0); for (int i = 1; i <= n1; i++) { // pre 保存 dp[i-1][j-1] 的值（左上角） int pre = 0; for (int j = 1; j <= n2; j++) { // temp 保存当前 dp[j]（即 dp[i-1][j]，正上方） int temp = dp[j]; if (text1[i - 1] == text2[j - 1]) { // 相等时，取左上角值+1 dp[j] = pre + 1; } else { // 不相等时，取正上方（temp）或正左方（dp[j-1]）的最大值 dp[j] = max(temp, dp[j - 1]); } // 更新pre为下一轮的左上角值（当前的dp[j]原值） pre = temp; } } return dp[n2]; } }; -
也可以使用两个一维数组来优化空间
class Solution { public: int longestCommonSubsequence(string s, string t) { // n是s的长度，m是t的长度 int n = s.size(), m = t.size(); // 定义两行数组f：f[0]和f[1]，每行长度为m+1，初始值默认0（符合LCS边界条件） vector f(2, vector<int>(m + 1)); // 遍历s的每个字符（i对应s的第i个字符，从0开始） for (int i = 0; i < n; i++) { // 遍历t的每个字符（j对应t的第j个字符，从0开始） for (int j = 0; j < m; j++) { // 核心状态转移： // (i+1)%2 表示当前行，i%2 表示上一行 if (s[i] == t[j]) { // 字符相等：当前值 = 上一行左上角值 + 1 f[(i + 1) % 2][j + 1] = f[i % 2][j] + 1; } else { // 字符不等：当前值 = 上一行正上方 值 或 当前行正左方 值 的最大值 f[(i + 1) % 2][j + 1] = max(f[i % 2][j + 1], f[(i + 1) % 2][j]); } } } // 最终结果存在最后一行的最后一列（n%2确定最后一行是0还是1） return f[n % 2][m]; } }; -
原始二维 DP 中，计算第
i+1行的值时，只依赖第i行的数据，因此不需要保存所有行，只需保存 “当前行” 和 “上一行” -
用
(i+1)%2和i%2来切换两行：- 当
i是偶数（0,2,4...）：i%2=0（上一行是 f [0]），(i+1)%2=1（当前行是 f [1]）； - 当
i是奇数（1,3,5...）：i%2=1（上一行是 f [1]），(i+1)%2=0（当前行是 f [0]）
- 当
-
这种取模操作实现了两行数组的 “循环复用”，避免了额外的空间开销
-
原始二维 DP 中，
dp[i+1][j+1]对应s[0..i]和t[0..j]的 LCS 长度；这里f[(i+1)%2][j+1]完全等价于原始的dp[i+1][j+1]，只是用两行数组替代了二维数组 -
数组
f初始化为全 0，对应原始二维 DP 中第一行（i=0）和第一列（j=0）的边界（空字符串与任意字符串的 LCS 长度为 0），无需额外处理 -
进一步地，用范围遍历简化
s的循环，把pre变量的定义放到内层循环里，最终实现了逻辑不变但代码更简洁的一维数组优化方案class Solution { public: int longestCommonSubsequence(string s, string t) { // m是字符串t的长度，后续一维数组f的长度为m+1（对应t的0~m列） int m = t.size(); // 一维DP数组f，初始全0（对应空字符串的边界条件） vector<int> f(m + 1); // 范围遍历s的每个字符x（等价于for(int i=0; i<s.size(); i++) { char x = s[i]; }） for (char x : s) { // 内层循环：j遍历t的每个字符（0~m-1），pre初始化为0（保存左上角dp[i-1][j-1]的值） for (int j = 0, pre = 0; j < m; j++) { // tmp暂存f[j+1]的原值（即上一行的dp[i-1][j+1]，正上方的值） int tmp = f[j + 1]; // 核心状态转移： // 若当前字符相等 → 取左上角(pre)+1；否则 → 取正上方(f[j+1])或正左方(f[j])的最大值 f[j + 1] = x == t[j] ? pre + 1 : max(f[j + 1], f[j]); // 更新pre为当前tmp（即下一轮j的左上角值） pre = tmp; } } // 最终结果存在f[m]（对应t的最后一列） return f[m]; } };
计算最长公共子序列的个数
-
要计算最长公共子序列的个数，需要维护两个 DP 数组：
dp_len[i][j]：表示s[0..i-1]和t[0..j-1]的最长公共子序列长度；dp_cnt[i][j]：表示s[0..i-1]和t[0..j-1]的最长公共子序列的个数
-
核心状态转移逻辑：
- 当 s [i-1] == t [j-1]：
dp_len[i][j] = dp_len[i-1][j-1] + 1（长度 + 1）；dp_cnt[i][j] = dp_cnt[i-1][j-1]（个数等于左上角的个数）；
- 当 s [i-1] != t [j-1]：
dp_len[i][j] = max(dp_len[i-1][j], dp_len[i][j-1])（长度取最大值）；- 若
dp_len[i-1][j] > dp_len[i][j-1]：dp_cnt[i][j] = dp_cnt[i-1][j]（个数取上方的）； - 若
dp_len[i][j-1] > dp_len[i-1][j]：dp_cnt[i][j] = dp_cnt[i][j-1]（个数取左方的）； - 若
dp_len[i-1][j] == dp_len[i][j-1]：dp_cnt[i][j] = dp_cnt[i-1][j] + dp_cnt[i][j-1]（个数相加，需去重）
- 关键注意点：需要去重（避免重复计数）—— 当
s[i-1] != t[j-1]且dp_len[i-1][j] == dp_len[i][j-1]时，若dp_len[i-1][j-1] == dp_len[i][j]，需要减去dp_cnt[i-1][j-1]（因为这部分被重复计算了）
- 当 s [i-1] == t [j-1]：
-
代码实习
const int MOD = 1e8; class Solution { public: int numDistinctLCS(string s, string t) { int n = s.size(), m = t.size(); // dp_len[i][j]：s[0..i-1]和t[0..j-1]的LCS长度 vector<vector<int>> dp_len(n + 1, vector<int>(m + 1, 0)); // dp_cnt[i][j]：s[0..i-1]和t[0..j-1]的LCS个数，初始化为1（空序列也算1种） vector<vector<long long>> dp_cnt(n + 1, vector<long long>(m + 1, 1)); // 初始化边界：空字符串和任意字符串的LCS个数为1（只有空序列） for (int i = 1; i <= n; i++) dp_cnt[i][0] = 1; for (int j = 1; j <= m; j++) dp_cnt[0][j] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (s[i-1] == t[j-1]) { // 字符相等：长度=左上角+1，个数=左上角个数 dp_len[i][j] = dp_len[i-1][j-1] + 1; dp_cnt[i][j] = dp_cnt[i-1][j-1]; } else { // 字符不等：先取长度的最大值 dp_len[i][j] = max(dp_len[i-1][j], dp_len[i][j-1]); // 初始化个数为0 dp_cnt[i][j] = 0; // 上方长度等于最大值，累加上方个数 if (dp_len[i-1][j] == dp_len[i][j]) { dp_cnt[i][j] += dp_cnt[i-1][j]; dp_cnt[i][j] %= MOD; } // 左方长度等于最大值，累加左方个数 if (dp_len[i][j-1] == dp_len[i][j]) { dp_cnt[i][j] += dp_cnt[i][j-1]; dp_cnt[i][j] %= MOD; } // 去重：如果左上角长度也等于最大值，减去重复计数的部分 if (dp_len[i-1][j-1] == dp_len[i][j]) { dp_cnt[i][j] -= dp_cnt[i-1][j-1]; dp_cnt[i][j] %= MOD; } } } } // 返回最终个数（转int，题目一般不要求大数，若需大数可返回long long） return (int)dp_cnt[n][m]; } }; -
空间优化
#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; const int MOD = 1e8; pair<int, int> longestCommonSubsequenceWithCount(string s, string t) { int n = s.size(), m = t.size(); // 优化：让较短的字符串作为t，减少一维数组长度 if (n < m) { swap(s, t); swap(n, m); } // 一维DP数组：保存长度和个数 vector<int> dp_len(m + 1, 0); vector<long long> dp_cnt(m + 1, 1); // 边界：空序列个数为1 for (int i = 1; i <= n; ++i) { // pre_len: 左上角(dp_len[i-1][j-1])，pre_cnt: 左上角(dp_cnt[i-1][j-1]) int pre_len = 0; long long pre_cnt = 1; for (int j = 1; j <= m; ++j) { // 暂存当前j位置的原始值（即dp_len[i-1][j]和dp_cnt[i-1][j]） int curr_len = dp_len[j]; long long curr_cnt = dp_cnt[j]; if (s[i-1] == t[j-1]) { // 字符相等：长度=左上角+1，个数=左上角个数 dp_len[j] = pre_len + 1; dp_cnt[j] = pre_cnt % MOD; } else { // 字符不等：长度取上方/左方最大值 dp_len[j] = max(dp_len[j], dp_len[j-1]); dp_cnt[j] = 0; // 上方长度等于最大值，累加上方个数 if (curr_len == dp_len[j]) { dp_cnt[j] = (dp_cnt[j] + curr_cnt) % MOD; } // 左方长度等于最大值，累加左方个数 if (dp_len[j-1] == dp_len[j]) { dp_cnt[j] = (dp_cnt[j] + dp_cnt[j-1]) % MOD; } // 去重：左上角长度等于最大值时，减去重复计数 if (pre_len == dp_len[j]) { dp_cnt[j] = (dp_cnt[j] - pre_cnt + MOD) % MOD; } } // 更新左上角值，供下一个j使用 pre_len = curr_len; pre_cnt = curr_cnt; } } // 返回长度和取余后的个数 return {dp_len[m], (int)(dp_cnt[m] % MOD)}; }
这篇文档有帮助吗？