最长公共子序列
最长公共子序列
思路:想一想 没什么思路的话看yxc DP分析法了。这道题绝壁百分之百刷过。
AcWing 897. 最长公共子序列 - AcWing这篇题解我觉得讲的挺好的。可以多看看。
代码：
const int N = 1010;
int dp[N][N];//dp[i][j] 表示第一个序列从1到i和第二个序列从1到j的公共子序列的集合中 的最长的值。
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
for(int i=1;i<=text1.length();i++)
{
for(int j=1;j<=text2.length();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[text1.length()][text2.length()];
}
};