少年Q

用户名：yin19990129

访问量：22589

签　名：

这次一定不水了！

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

　　自我简介：

TA的其他文章

36.奔跑的野猪-题解(C++代码)只做最好的思路！
浏览：212

38.神之设备（C++代码）只做最好的思路！
浏览：231

40.殊途同归（C++代码）只做最好的思路！
浏览：443

你可能喜欢

A+B for Input-Output Practice (IV) （C语言代码）

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

优质题解

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

　　作者: 少年Q　　　　发表时间：2020-04-16 08:42:51 浏览：1239　|　评论：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分

20 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问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二级辅导-同因查找（C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

【数组的距离】（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

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

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

评论区

精彩推荐

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

C语言训练-计算1977！* （C++代码）

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

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

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

简单的for循环

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

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

矩阵加法（C语言代码）

1071题解

少年Q

TA的其他文章

你可能喜欢

C二级辅导-同因查找 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

【数组的距离】 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

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

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

评论区

精彩推荐

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

C语言训练-计算1977！* （C++代码）

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

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

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

简单的for循环

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

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

矩阵加法 （C语言代码）

1071题解

C二级辅导-同因查找（C语言代码）

【数组的距离】（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

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

　　评论区

矩阵加法（C语言代码）