最长公共子序列指的是两个字符串中都存在的最长的子序列，子序列不需要连续，只要顺序一致即可。使用动态规划解决这个问题的核心是通过状态转移逐步推导结果。
动态规划思路拆解
状态定义
我们定义二维数组dp[i][j]，表示第一个字符串的前i个字符和第二个字符串的前j个字符的最长公共子序列的长度。这里需要注意，字符串的下标通常从0开始，而dp数组的维度会比字符串长度多1，用来处理边界情况。
状态转移方程
对于两个字符串str1和str2，当遍历到str1的第i-1位和str2的第j-1位时：
- 如果两个字符相等，那么
dp[i][j] = dp[i-1][j-1] + 1，相当于在之前的最长公共子序列基础上加上这个相同的字符 - 如果两个字符不相等，那么
dp[i][j] = max(dp[i-1][j], dp[i][j-1])，取去掉str1当前字符或者去掉str2当前字符的情况下的最长公共子序列的最大值
边界条件
当i为0或者j为0时，说明其中一个字符串没有字符，此时最长公共子序列长度为0，所以dp[0][*]和dp[*][0]的所有值都为0。
完整代码实现
下面的代码不仅实现了最长公共子序列长度的计算，还实现了回溯输出具体的最长公共子序列内容：
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 计算最长公共子序列长度并输出具体序列
void lcs(string str1, string str2) {
int m = str1.size();
int n = str2.size();
// 定义dp数组，初始化为0
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// 填充dp数组
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// 输出最长公共子序列长度
cout << "最长公共子序列长度为：" << dp[m][n] << endl;
// 回溯获取具体的最长公共子序列
if (dp[m][n] == 0) {
cout << "最长公共子序列为空" << endl;
return;
}
string result = "";
int i = m, j = n;
while (i > 0 && j > 0) {
if (str1[i - 1] == str2[j - 1]) {
// 当前字符属于公共子序列，加入结果
result.push_back(str1[i - 1]);
i--;
j--;
} else {
// 取dp值更大的方向回溯
if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
}
// 反转结果，因为我们是从后往前添加的字符
reverse(result.begin(), result.end());
cout << "最长公共子序列为：" << result << endl;
}
int main() {
string str1 = "abcde";
string str2 = "ace";
lcs(str1, str2);
return 0;
}
代码运行说明
上述代码中，我们传入的两个测试字符串分别是abcde和ace，运行后会输出最长公共子序列长度为3，具体序列为ace。如果修改输入的字符串，算法也能正确计算出对应的最长公共子序列。这个实现的时间复杂度是O(m*n)，空间复杂度也是O(m*n)，其中m和n分别是两个输入字符串的长度。