最长公共子序列
最长公共子序列:给定两个序列S1和S2,求二者公共子序列S3的最长的长度。
有了前面的基础,可以发现这个问题仍然可以按照序列的长度来划分状态,也就是S1的前i个字符和S2的前j个字符的最长公共子序列长度,记为lcs[i[j]。
如果S1的第i项,和S2的第j项相同,那么S1[i]与S2[j]作为公共子序列的末尾,则
lcs[i][j]= lcs[i-1][j-1]+1
也可以不让S1[i]与S2[j]作为公共子序列的末尾,则
lcs[i][i] = max(lcs[i][j-1],Ics[i-1][i])
不难证明:
max(lcs[i][j-1],Ics[i-1][j])< Ics[i-1][j-1]+1
那么转移方程是:
举一个例子,两个序列 S1 = abcfbc和S2 = abfcab,根据转移方程可以得出 lcs[i][j]
实现代码:
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int dp[110][110];
int main()
{
string a, b;
memset(dp, 0, sizeof(dp));
cin >> a >> b;
int lena = a.size();
int lenb = b.size();
for (int i = 1; i <= lena; i++)
{
for (int j = 1; j <= lenb; j++)
{
if (a[i - 1] == b[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[lena][lenb] << endl;
return 0;
}