mrzs

用户名：mrzs

访问量：5194

签　名：

等　　级
排　　名	2048
经　　验	2485
参赛次数	0
文章发表	4
年　　龄	19
在职情况	学生
学　　校	湖北专职专高
专　　业	电脑

　　自我简介：

千年琵琶万年筝，HelloWorld练一生。

TA的其他文章

最长公共子序列
浏览：158

校门外的树---模拟
浏览：2493

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

最长公共子序列

　　作者: mrzs　　　　发表时间：2020-04-20 17:03:07 浏览：158　|　评论：0　

原题链接：蓝桥杯算法提高VIP-最长公共子序列

##动规一直是玄学（二）

###动规入门----最长公共子序列问题

#问题定义
####定义：` L(n1,n2)` 为A串的前n1个字符，和B串的前n2个字符的最大公共子序列长度。（很重要！！）
######如： abcdgh 与 abhdbf 的 `L(1,2) = 1` （a 与 ab 的最长公共子序列 只有a）
#寻找子问题依赖
已知： `L ( n1-1,n2-1 )`和 `L(n1-1,n2)` 和  `L(n1,n2-1)`
求出： `L (n1,n2)`

###分析
设`A[i] `为A串第 i 个元素， `B[i]` 为B串第 i 个元素
1. 若 `A[n1]==B[n2]` 即A、B串的尾部元素相同，此时 ①`L(n1,n2)= L（n1-1,n2-1）+ 1` 即两个串分别加上这个字符之前的最长公共子序列长度(定义) + 1
例如： abcd 与 abd (去掉d ) => abc 与 ab （点到为止，不详讲）
2. 若 `A[n1]！=B[n2]` 尾部元素不同。那么到达 `L (n1,n2)` 有两个方向，
一是在 `L (n1-1,n2)` 处，给A串尾部加上一个字符变成 `L (n1,n2)` 
二是在 `L (n1-1,n2)` 处，给B串尾部加上一个字符变成 `L (n1,n2)`
此时 ②`L (n1,n2) = Max（ L (n1-1,n2)，L (n1,n2-1) ）`

####程序如下： (包含填表过程，自行运行)
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
using namespace std;
int dp[1001][1001]={0};
int main(){
	char a[1001];
	char b[1001];
	cin>>a;
	cin>>b;	
	int la=strlen(a);
	int lb=strlen(b);

for(int i=0;i<la;i++){
		for(int j=0;j<lb;j++){
			if(a[i]!=b[j])
				dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
			else dp[i+1][j+1]=dp[i][j]+1;
		}
	/*	for(int i=1;i<=la;i++){
			for(int j=1;j<=lb;j++){
				cout<<dp[i][j]<<' ';
			}							//打印填表过程 
			cout<<endl;
		}
		cout<<endl;
	}*/
	cout<<dp[la][lb];
	return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

mrzs

TA的其他文章

你可能喜欢

明明的随机数（C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

假币问题（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

C二级辅导-阶乘数列（C语言代码）

最长公共子序列

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

川哥的吩咐（C语言代码）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

简单的a+b （C语言代码）

sizeof的大作用（C语言代码）

GC的苦恼（C语言代码）

筛排处理（C语言代码）

三角形（C语言代码）

mrzs

TA的其他文章

你可能喜欢

明明的随机数 （C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

假币问题 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

C二级辅导-阶乘数列 （C语言代码）

最长公共子序列

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.9 （C语言代码） 用函数传参的方法

川哥的吩咐 （C语言代码）

C语言训练-计算：t=1-1/(2*2)-1/(3*3)-...-1/(m*m) （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

简单的a+b （C语言代码）

sizeof的大作用 （C语言代码）

GC的苦恼 （C语言代码）

筛排处理 （C语言代码）

三角形 （C语言代码）

明明的随机数（C++代码）

假币问题（C语言代码）

C二级辅导-阶乘数列（C语言代码）

　　评论区

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

川哥的吩咐（C语言代码）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

sizeof的大作用（C语言代码）

GC的苦恼（C语言代码）

筛排处理（C语言代码）

三角形（C语言代码）