最长公共子序列是一个最基础的Dp,要想搞懂他可以手动模拟一下，很有效。
下面用一个maxlen的二维数组来记录我们的比较情况， maxlen[i][j]记录的就是两个字符串 s1的前 i个字符与s2前 j 个字符的最长公共子序列；
下面介绍下最重要的两个步骤：
if(s1[i] == s2[j])
maxlen[i][j] = maxlen[i-1][j-1] + 1;
这个步骤的意思如果字符串s1的第 i 个字符与 s2 的第 j 个字符相同，那么字符串 s1的前 i个字符与s2前 j 个字符的最长公共子序列就应该是字符串 s1的前 i-1 个字符与s2前 j -1 个字符的最长公共子序列 .
else
maxlen[i][j] = max(maxlen[i][j-1],maxlen[i-1][j]);
这个步骤的意思如果字符串s1的第 i 个字符与 s2 的第 j 个字符不相同，那么字符串 s1的前 i个字符与s2前 j 个字符的最长公共子序列就应该是字符串s1的前 i-1 个字符与s2前 j 个字符的最长公共子序列 和 字符串s1的前 i个字符与s2前 j -1 个字符的最长公共子序列的最大值。
参考代码：
#include<stdio.h>
#include<string.h>
using namespace std;
const int N = 1000;
char s1[N], s2[N]; //两个字符串
int maxlen[N][N];
int max(int a,int b)
{
if(a>b)
return a;
return b;
}
int main()
{
scanf("%s %s",s1+1,s2+1); // 输入字符串，下标从 1 开始
int i, j, len1, len2;
len1 = strlen(s1+1); // s1 的长度
len2 = strlen(s2+1);// s2 的长度
memset(maxlen,0,sizeof(maxlen));
for(i=1; i<=len1; i++)
for(j=1; j<=len2; j++)
{
if(s1[i] == s2[j])
maxlen[i][j] = maxlen[i-1][j-1] + 1;
else
maxlen[i][j] = max(maxlen[i][j-1],maxlen[i-1][j]);
}
printf("%d\n",maxlen[len1][len2]);
return 0;
}