commom subsequence题解

题目描述：

给定两个字符串s1和s2，找到它们的最长公共子序列（LCS），并返回其长度。

我们定义一个序列为s1的子序列，当且仅当通过删除s1中的某些字符而不改变其余字符的相对顺序可以得到。例如，"ace"是"abcde"的子序列，但"aec"不是。

一个字符串的子序列是通过删除一些（也可以不删除）字符而不改变剩余字符的相对顺序得到的新字符串。

例如，"ace"是"abcde"的子序列，但"aec"不是。

题解：

动态规划的思想。我们用dp[i][j]表示s1的前i个字符和s2的前j个字符的LCS的长度。如果s1[i-1]和s2[j-1]相等，则dp[i][j] = dp[i-1][j-1] + 1，即s1和s2中i-1和j-1位置上的字符在LCS中，故LCS长度加1；如果s1[i-1]和s2[j-1]不相等，则dp[i][j] = max(dp[i-1][j], dp[i][j-1])，即在s1的前i-1个字符和s2的前j个字符的LCS长度和s1的前i个字符和s2的前j-1个字符的LCS长度中取最大值。

C++代码：

class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1));
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];
}
};