hdu1159最长公共子序列lcs

评测点

HDU1159

题目

「题意」
求两个字符串最长公共子序列的长度,
最长公共子序列强调位置的前后关系不变,
但不在乎是否连续,不唯一
「输入样例」
abbccdss aeebfcaadb
「输出样例」
4

某解释

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
char s[1010],s1[1010];
int f[1010][1010];
int (int argc, char *argv[])
{
scanf("%s %s",s+1,s1+1);
int l1=strlen(s+1),l2=strlen(s1+1);
for(int i=1;i<=l1;i++)
for(int j=1;j<=l2;j++)
{
if(s[i]==s1[j]) f[i][j]=f[i-1][j-1]+1;
else f[i][j]=mymax(f[i-1][j],f[i][j-1]);
}
printf("%d",f[l1][l2]);
}

分析:
a=abc
b=1abc
n=3
m=4
i=2 4//字符串2的位置
j=2 3//字符串1的位置
s=
0 0 0 0
1 1 1 1
0 2 2 2
0 0 3 3