少年Q

用户名：yin19990129

访问量：25370

签　名：

这次一定不水了！

等　　级
排　　名	181
经　　验	6821
参赛次数	2
文章发表	71
年　　龄	21
在职情况	学生
学　　校	宿迁学院
专　　业	软件工程

　　自我简介：

TA的其他文章

[传智杯]软件工程实习（C++描述）只做最好的思路！
浏览：380

[传智杯]程序员节发橙子（C++描述）只做最好的思路！
浏览：487

[传智杯]众数出现的次数-题解(C++代码)只做最好的思路！
浏览：191

你可能喜欢

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

蓝桥杯算法提高VIP-最长公共子序列（C++描述）只做最好的思路！

　　作者: 少年Q　　　　发表时间：2020-04-16 08:42:51 浏览：1487　|　评论：4　

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

这题也算是比较简单的dp，如果感觉不能一下推出状态转移方程，那么可以画表格来分析，从而得出状态转移方程，下面演示下c数组的填表过程：（以求ABCB和BDCA的LCS长度为例）：
![](/image_editor_upload/20200416082812_62463.jpg)
![](/image_editor_upload/20200416082911_44851.jpg)
![](/image_editor_upload/20200416083007_89122.jpg)
![](/image_editor_upload/20200416083137_39249.jpg)
![](/image_editor_upload/20200416083208_14020.jpg)
![](/image_editor_upload/20200416083232_88300.jpg)
![](/image_editor_upload/20200416083311_38850.jpg)
![](/image_editor_upload/20200416083514_95900.jpg)
![](/image_editor_upload/20200416083542_20617.jpg)
![](/image_editor_upload/20200416083603_39506.jpg)
![](/image_editor_upload/20200416083630_49662.jpg)
![](/image_editor_upload/20200416083657_40113.jpg)
依次类推，最后填出的表为：
![](/image_editor_upload/20200416083809_91542.jpg)
右下角的2即为LCS的长度。
根据表格的规律，我们列出状态转移方程：
![](/image_editor_upload/20200416084138_20929.jpg)
根据状态转移方程的描述，我们码出代码，如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int main(){
	string s1,s2;
	cin>>s1>>s2;
	for(int i=1;i<=s1.size();i++){
		for(int j=1;j<=s2.size();j++){
			if(s1[i-1]==s2[j-1]){
				dp[i][j]=dp[i-1][j-1]+1;
			}else{
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
	}
	cout<<dp[s1.size()][s2.size()]<<endl;
	return 0;
}
```

0.0分

21 人评分

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

　　评论区

迟迟

为什么一样就要左上角的值加1？求告知

2022-12-23 11:30:57

夜猫子的自救

把bp数组放到int main（）中为啥不行啊？

2022-04-05 18:13:11

夜猫子的自救

怎么想到的，太厉害了

2022-04-05 16:40:31

卷某

厉害了

2021-05-10 16:01:04

少年Q

TA的其他文章

你可能喜欢

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

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

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

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

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

蓝桥杯算法提高VIP-最长公共子序列（C++描述）只做最好的思路！

评论区

精彩推荐

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

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）直接打表啊8以上值不变hhh

格式错误一万年，，有没有过了的来看看（终于过了）

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

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

C语言训练-斐波纳契数列（C语言代码）

钟神赛车（C语言代码）

C语言训练-求素数问题（C语言代码）

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

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

少年Q

TA的其他文章

你可能喜欢

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

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

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

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

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

蓝桥杯算法提高VIP-最长公共子序列 （C++描述）只做最好的思路！

评论区

精彩推荐

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

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）直接打表啊8以上值不变hhh

格式错误一万年，，有没有过了的来看看（终于过了）

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

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

C语言训练-斐波纳契数列 （C语言代码）

钟神赛车 （C语言代码）

C语言训练-求素数问题 （C语言代码）

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

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

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

蓝桥杯算法提高VIP-最长公共子序列（C++描述）只做最好的思路！

　　评论区

C语言训练-斐波纳契数列（C语言代码）

钟神赛车（C语言代码）

C语言训练-求素数问题（C语言代码）