SDUT 2080 最长公共子序列问题

动态规划。

注意输入数据中有空格。

代码如下：

 1 #include
 2 #include
 3 #include
 4 
 5 using namespace std;
 6 
 7 int len[1000][1000];
 8 
 9 int main()
10 {
11     int i, j, alen, blen;
12     char s1[1000], s2[1000];
13     while(gets(s1))
14     {
15         gets(s2);
16         alen=strlen(s1);
17         blen=strlen(s2);
18         for (i=0; i<=alen; i++)
19             len[i][0]=0;
20         for (j=0; j<=blen; j++)
21             len[0][j]=0;
22         for (i=1; i<=alen; i++)
23         {
24             for (j=1; j<=blen; j++)
25             {
26                 if (s1[i-1] == s2[j-1])
27                     len[i][j]=len[i-1][j-1]+1;
28                 else
29                     len[i][j]=max(len[i][j-1], len[i-1][j]);
30             }
31         }
32         cout << len[alen][blen] << endl;
33     }
34     return 0;
35 }

转载于:https://www.cnblogs.com/zrq495/archive/2012/08/10/2632767.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！