1265：【例9.9】最长公共子序列_1265:【例9.9】最长公共子序列

题目链接在此：
http://ybt.ssoier.cn:8088/problem_show.php?pid=1265

这里给出两种解法，分析过程网上有，这里不赘述：
第一种是二维的

#include<bits/stdc++.h>
using namespace std;
char a[1001],b[1001];
int lena,lenb,dp[1001][1001];
int main(){
	scanf("%s%s",a+1,b+1);
	lena=strlen(a+1);
	lenb=strlen(b+1);
	for(int i=1;i<=lena;i++){
		for(int j=1;j<=lenb;j++){
			if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1;
			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);	//状态转移方程
		}
	}
	printf("%d",dp[lena][lenb]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

通过第一种代码发现，dp[i][j] 的状态只与 dp[i][j-1] , dp[i-1][j] , dp[i-1][j-1] 的状态有关，故可以利用一个变量存储 dp[i-1][j-1] 的状态，将二维降至一维。

上代码：

#include<bits/stdc++.h>
using namespace std;
char a[1001],b[1001];
int lena,lenb,dp[1001],temp,t;
int main(){
	scanf("%s%s",a+1,b+1);
	lena=strlen(a+1);
	lenb=strlen(b+1);
	for(int i=1;i<=lena;i++){
		t = 0;
		for(int j=1;j<=lenb;j++){
			temp = dp[j];
			if(a[i]==b[j])dp[j]=t+1;
			else dp[j]=max(dp[j],dp[j-1]);
			t=temp;				//重点是这一块
		}
	}
	printf("%d",dp[lenb]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

小盆友们学废了吗？