最长公共子序列(题号：3587)时间限制200ms，空间限制131072KB

常规
1

题目描述

时间：0.2s 空间：32M

题目描述：

给你两个字符串，求这两个串的最长公共子序列。

对于字符串abcde

acd，ace， ade等都是子序列，acb不是子序列《——看不懂

输入格式：

输入两行，每行包含一个字符串

输出格式：

输出一个整数表示最长公共子序列的长度
样例输入1：

xjoixjoi
joyjoy

样例输出1：

4

样例输入2：

xsrrnzkbhzkhzmvkjevsrbdiclckmsgpgngyckzvgysvwcgwayjokqactfxtivfbdwprufivtgg zhbpvlxfkisdneogdseenjlewrobjhpppjczyxeaiqanaztksnpfwyhdjvipgwzznmnnxwraiiei

样例输出2：

21

看不懂啊

线性dp！

2

跳转原题！

3

用string和string截取来判断

4

先写一下看看

5

是要函数？
还是程序

6

我正在写。。。。。。

7

呃

#include <iostream>
using namespace std;

string x, y;
int ans,dp[100005];
int main() {
	cin >> x >> y;
    x += "0";
    y += "0";
	for (int i = 1; i < x.size(); i++) {
		for (int j = 1; j < y.size(); j++) {
			if(x[i] == b[j]) dp[i][j] ++;
		}
	}

}
8

**一个图灵写好久

9

是 AC 代码？

10

哦，原来是动态规划

12

AC代码点击

#include <iostream>
using namespace std;

string x, y;
int ans, dp[1005][1005];
int main() {
	cin >> x >> y;
	x += "0";
	y += "0";
	for (int i = 1; i < x.size(); i++) {
		for (int j = 1; j < y.size(); j++) {
			if (x[i] == y[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = dp[i][j - 1];
		}
	}

}

输出不会啊

13

(doge)

14

OKAC了（AC代码）

15

@徐熙喆 关贴

16
17

发帖太频繁了，警告