最长公共子序列问题

问题描述

给定两个字符串s1s2s3…sn和t1t2…tn。求出两个字符串最长的公共子序列的长度。字符串s1s2s3…sn的子序列指可以表示为si1si2…sim(i1<i2<…<im)的序列。 限制条件 1<=n,m<=1000

样例输入

4//n 4//m abcd//s brcd//t

样例输出

3//bcd

代码

#include <iostream> #include <algorithm> #include <string.h> #include <cstdio> using namespace std; int dp[1000][1000]; char s[1005],t[1005]; int main() { int n,m; scanf("%d%d",&n,&m); getchar(); for(int i = 0;i<n;i++) { scanf("%c",&s[i]); } getchar(); for(int i = 0;i<m;i++) { scanf("%c",&t[i]); } for(int i = 0;i<=n;i++) { for(int j = 0;j<=m;j++) { if(s[i]==t[j]) { dp[i+1][j+1] = dp[i][j]+1; } else { dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]); } } } printf("%d\n",dp[n][m]); return 0; }