CJOJ 2044 【一本通】最长公共子序列（动态规划）

Description

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X，则另一序列Z是X的子序列是指存在一个严格递增的下标序列 ，使得对于所有j=1,2,…,k有 Xij=Zj 。

例如，序列Z是序列X的子序列，相应的递增下标序列为<2,3,5,7>。 给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

最长公共子序列(LCS)问题：给定两个序列X=和Y=，要求找出X和Y的一个最长公共子序列。

Input

输入两行，每行由大写字母构成的长度不超过200的字符串，表示序列X和Y

Output

第一行非负整数N，表示最长公共子串的长度，若不存在公共子序列输出0.

第二行输出最长的公共子序列(若存在多个，输出最先出现的最长公共子序列)

Sample Input

ABCDDAB BDCABA

Sample Output

4

Http

CJOJ:http://oj.changjun.com.cn/problem/detail/pid/2044

Source

动态规划

解决思路

这道题是一道动态规划的经典题目。

我们定义F[i][j]表示字符串A的前i位和字符串B的前j位能取到的最长公共子序列，那么自然有F[i][0]均为0，F[0][i]也均为0。

首先我们可以确定的是对于任意的F[i][j]，均可以从F[i-1][j]（即字符串A减去一个字符）和F[i][j-1]（即字符串B减去一个字符）得到，所以必有F[i][j]=min(F[i-1][j]+F[i][j-1])。那么如果A[i]==B[j]，则说明F[i][j]还可以从F[i-1][j-1]推得。

所以，综上所述，动态转移方程就是\[F[i][j]=min(F[i-1][j-1],F[i-1][j],F[i][j-1]) (A[i]==B[j]) =min(F[i-1][j],F[i][j-1]) (Other)\]

另外，这道题的加强版在这里。因为数据范围的关系，不能在使用本题这种动态规划 的方法。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> using namespace std; const int maxN=300; const int inf=2147483647; string A; string B; int F[maxN][maxN]; int main() { memset(F,0,sizeof(F)); cin>>A>>B; for (int i=0;i<A.size();i++) F[i][0]=0; for (int i=0;i<B.size();i++) F[0][i]=0; for (int i=1;i<=A.size();i++) for (int j=1;j<=B.size();j++) if (A[i-1]==B[j-1]) { F[i][j]=max(F[i-1][j-1]+1,max(F[i-1][j],F[i][j-1])); } else F[i][j]=max(F[i-1][j],F[i][j-1]); cout<<F[A.size()][B.size()]<<endl; return 0; }

转载于:https://www.cnblogs.com/SYCstudio/p/7137828.html

相关资源：JAVA上百实例源码以及开源项目