首页 > 代码库 > Laoj P1196 最长公共子序列

Laoj P1196 最长公共子序列

2024-11-16 18:01:01   203人阅读

 

问题背景
动态规划入门-第15题  
 
试题描述
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=《x1,x2,……,xm》，则另一序列Z=《z1,z2,……,zk》是X的子序列是指存在一个严格递增的下标序列 《i1,i2,……,ik》，使得对于所有j=1,2,……,k有： 
Zj=Xij
例如，序列Z=《B,C,D,B》是序列X=《A,B,C,B,D,A,B》的子序列，相应的递增下标序列为《2,3,5,7》。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X=《A,B,C,B,D,A,B》和Y=《B,D,C,A,B,A》，则序列《B,C,A》是X和Y的一个公共子序列，序列《B,C,B,A》也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。 
给定两个序列X=《x1,x2,……,xm》和Y=《y1,y2,……,yn》，要求找出X和Y的一个最长公共子序列。 
输入格式
共有两行，每行为一个由大写字母构成的长度不超过200的字符串，表示序列X和Y。
输出格式
一个非负整数，表示所求得的最长公共子序列的长度，若不存在公共子序列，则仅输出一个整数0。
输入示例
ABCBDAB
BDCABA
输出示例
4

 

 

【分析】

dp入门，就是LCS啦，用的是白书上的思路，水过去。

 

 

【代码】

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 string s1, s2;
 5 int l1, l2, dp[205][205];
 6 
 7 int main() {
 8     memset(dp, 0, sizeof(dp));
 9     dp[0][0]=0;
10     cin >> s1 >> s2;
11     l1=s1.length(), l2=s2.length();
12     s1=" "+s1, s2=" "+s2;
13     for (int i=1;i<=l1;++i)
14         for (int j=1;j<=l2;++j){
15             if (s1[i]==s2[j])
16                 dp[i][j]=dp[i-1][j-1]+1;
17             else
18                 dp[i][j]=max(dp[i][j-1], dp[i-1][j]);
19         }
20     cout << dp[l1][l2] << endl;
21 }

 

Laoj P1196 最长公共子序列


联系
我们