1143. 最长公共子序列
3 min
题目
解法：动态规划
思路
核心思想是动态规划，通过构建二维DP表存储所有前缀子串的最优解。
正确性基于最优子结构：每个状态 dp[i][j] 都表示 text1 前 i 个字符与 text2 前 j 个字符的最长公共子序列长度。当字符匹配时，问题可分解为子问题 dp[i-1][j-1] 加1；不匹配时，最优解必然包含于跳过 text1[i-1] 或 text2[j-1] 的两种情况之一，因此取最大值可保证不遗漏最优解。
- Step 1: 初始化 (m+1)×(n+1) 的DP数组，全部置0
- Step 2: 双重循环遍历两个字符串的所有字符位置
- Step 3: 若当前字符匹配，则 dp[i][j] = dp[i-1][j-1] + 1
- Step 4: 若字符不匹配，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- Step 5: 返回 dp[m][n] 作为最终结果
复杂度
- 时间复杂度: ，其中 m 和 n 为两字符串长度，需填充整个DP表。
- 空间复杂度: ，用于存储二维DP数组。
代码
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size();
int 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];
}
};