C ++中最长的公共子序列
假设我们有两个字符串text1和text2，我们必须返回它们最长的公共子序列的长度。字符串的优先顺序是从原始字符串生成的新字符串，其中删除了一些字符，而不会更改其余字符的相对顺序。（因此，例如“abe”是“abcde”的子序列，而“adc”则不是）。两个琴弦的共同子序列是两个琴弦共同的子序列。因此，如果没有公共子序列，则返回0。如果输入类似“abcde”和“ace”，则结果将为3。
为了解决这个问题，我们将遵循以下步骤-
n：=s的大小，m：=x的大小
如果n为0或m为0，则返回0
s：=空字符串，与s串联
x：=空字符串，与x串联
ret：=0
定义阶数为（n+1）x（m+1）的矩阵dp
对于我在1到n范围内
dp[i，j]：=dp[i，j-1]和dp[i–1，j]的最大值
如果s[i]=x[j]，则
dp[i，j]：=dp[i，j]的最大值，1+dp[i–1，j–1]
对于1到m范围内的j
返回dp[n，m]
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestCommonSubsequence(string s, string x) {
int n = s.size();
int m = x.size();
if(!n || !m) return 0;
s = " " + s;
x = " " + x;
int ret = 0;
vector < vector <int> > dp(n + 1, vector <int>(m + 1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m ; j++){
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
if(s[i] == x[j]) {
dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
}
}
}
return dp[n][m];
}
};
main(){
Solution ob;
cout << (ob.longestCommonSubsequence("abcde", "ace"));
}输入值
"abcde" "ace"
输出结果
3