最长公共子序列——动态规划
转载:https://blog.****.net/someone_and_anyone/article/details/81044153
里面写的很清楚,里面的代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int MAXN = 1005;
int DP[MAXN][MAXN];
int main()
{
string a;
string b;
while(cin >> a >> b)
{
int l1 = a.size();
int l2 = b.size();
memset(DP, 0, sizeof(DP));
for(int i = 1; i <= l1; i++)
for(int j = 1; j <= l2; j++)
if(a[i - 1] == b[j - 1])
DP[i][j] =DP[i - 1][j - 1] + 1;
else
DP[i][j] = max(DP[i][j - 1], DP[i - 1][j]);
printf("%d\n", DP[l1][l2]);
}
return 0;
}
还有一张图片也表示的很清楚,如下。