# DP专题 3 | LCS最长公共子序列 - POJ 1458

DP题目太多，加快上题速度~~

Common Subsequence（公共子序列问题）

Description

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, ..., xm > another sequence Z = < z1, z2, ..., zk > is a subsequence of X if there exists a strictly increasing sequence < i1, i2, ..., ik > of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.

Input

The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct.

Output

For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.

Sample Input

```abcfbc         abfcab
programming    contest
abcd           mnp```

Sample Output

```4
2
0```

LCS算法是一个二维DP，核心思想是：

dp[i][j]表示数列A[1~i]和数列B[1~j]的最长子序列长度。

```#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

int d[1000][1000];
string s1, s2;

int dp(int i, int j)
{
if(d[i][j] != -1)
return d[i][j];

if(i==0 || j==0)
return 0;

if(s1[i-1] == s2[j-1])
d[i][j] = dp(i-1, j-1) + 1;
else
d[i][j] = std::max(dp(i-1, j), dp(i, j-1));

return d[i][j];
}

int main()
{
while(cin>>s1>>s2)
{
memset(d, -1, sizeof(d));
cout << dp(s1.length(), s2.length()) <<endl;
}

return 0;
}```

```#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

char s1[1000];
char s2[1000];
int dp[1000][1000];

int main() {
while (cin >> s1 >> s2) {
int l1 = strlen(s1);
int l2 = strlen(s2);
int i, j;

for (i = 0; i <= l1; i++)
dp[i][0] = 0;

for (j = 0; j <= l2; j++)
dp[0][j] = 0;

for (i = 1; i <= l1; i++) {
for (j = 1; j <= l2; 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[l1][l2] << endl;
}
return 0;
}```

0 条评论

• ### DP专题 | 数字三角形 - POJ 1163

从本篇开始，准备做一系列的专题讲解，主要参考《算法竞赛入门经典》、《算法竞赛进阶指南》两本书。主要是为了能够更加系统的讲解各个知识点，这两本书已经讲得很好了，建...

• ### 最长上升子序列（LIS）算法

LIS（Longest Increasing Subsequence）最长上升子序列 一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列...

• ### 新手ACM算法学习建议

一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功。ACM主要是考算法的，主要时间是花在思考算法上，不是花在写程序与debug上。

• ### HUST 1602 - Substring

题目描述 This problem is quiet easy. Initially, there is a string A. Then we do ...

• ### 动态 | DeepMind 首次披露旗下专利申请情况

近日，DeepMind首次披露了一系列国际专利，这些专利涉及了现代机器学习的一些基础方面，对在人工智能领域进行商业化的任何人都有着潜在的意义。

• ### 项目经验不重样！3个基于 SpringBoot 的图片识别处理系统送给你！

最近看了太多读者小伙伴的简历，发现各种商城/秒杀系统/在线教育系统真的是挺多的。推荐一下昨晚找的几个还不错的基于 Java 的图片识别处理系统。

• ### 工欲善其事，必先利其器

随着嵌入式开发技术的进步，产品功能的越来越复杂，传统全靠工程师手动编码测试，验证的开发模式俨然已经无法满足开发中大型工程的需求，急需改变传统模式寻求新的模式和方...

• ### Sequelize 傻瓜式操作

模型的all方法，返回表中的所有数据 User .findOne({//还有find、findAll等方法 where: ...

• ### 一湖数据，几度春秋

2017年底的一场reorg，让微软的Azure Data Lake（数据湖）队伍拆的七零八落，Raghu Ramakrishnan也黯然神伤，被reorg成了...