P2543

题目

题目描述：

输入格式：

输入文件中包含两个字符串X和Y。当中两字符串非0即1。序列长度均小于9999。

输出格式：

X和Y的最长公共子序列长度。

数据范围与说明：

输入输出样例 #1

输入：

1
01010101010 00000011111

输出：

1
6

输入输出样例 #2

输入：

1
01011 010010101111111111

输出：

1
5

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
int dp[10001][10001];
int main(){
    string s1;
    string s2;
    int cnt=0;
    cin>>s1>>s2;
    for(int i=1;i<=s1.size();i++){
        for(int j=1;j<=s2.size();j++){
            if(s1[i-1]==s2[j-1])    dp[i][j]=dp[i-1][j-1]+1;
            else    dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
        }
    }
    cout<<dp[s1.size()][s2.size()];
    return 0;
}