SDUTOJ2080（动态规划）：最长公共子序列

SDUTOJ2080（动态规划）：最长公共子序列

========================

题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
最长公共子序列问题
Description
给定两个序列 X={x1,x2,…,xm} 和 Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

Input
输入数据有多组，每组有两行 ，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,Z）），表示序列X和Y。

Output
每组输出一行，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出0。

Sample
Input 
ABCBDAB
BDCABA
Output 
4

我的代码

1
//比较简单，这里做记录即可

心得： 这是一道比较经典的动规题，难度低。

思路

1
2
3
4
5
6
7
8
状态表示：我们用dp[i][j]表示数字A[1,i]与B[1,j] 的最长公共子序列长度。
分析：
当s1[i]=s2[j]时 dp[i][j]=d[i-1][j-1]+1; 因为相同时肯定是最长公共子序列长度+1；
当s1[i]!=s2[j]时 dp[i][j]=max(dp[i][j-1],dp[i-1][j]) 举个例子：
ABC A
ABD C
可得dp[4][4]=dp[3][4];
有一点小问题：有一些人认为不用考虑s1[i]==s2[j]的这种情况，因为dp[i-1][j]=dp[i-2][j]+dp[i-1][j-1] 也就是说else后面的这一种情况全部都可以包括，但我不这么认为，原因如下：如果只有else后面的语句得出的结果是0，我们建立表格时发现整个表格全部为零，我结合if里的语句简单的分析了一下，else语句的dp数组建立的表格确实能包括dp[i][j]但是从问题的角度来分析，s1[i]=s2[j]这种情况并没有被包括，就和贪心一样指一种情况对结果有一定的贡献所以不能舍弃（一点小的见解，仅供参考）

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <string.h>
using namespace std;
const int N=505;
int dp[N][N];
char s1[N],s2[N];

int main()
{
    int n,m;
    while(~scanf("%s %s",s1+1,s2+1)){
        n=strlen(s1+1);
        m=strlen(s2+1);  //数组统一往后移动一位是考虑到边界问题
        for(int i=0;i<n;i++) dp[i][0]=0;
        for(int j=0;j<m;j++) dp[0][j]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s1[i]==s2[j])   
                 {
                     dp[i][j]=dp[i-1][j-1]+1;
                 }
                 else 
                 {
                     dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                 }
            }
        }
        printf("%d\n",dp[n][m]);
    }
    return 0;
 }

题目链接：https://acm.sdut.edu.cn/onlinejudge3/problems/2080