C++动态规划之最长上升子序列

这篇具有很好参考价值的文章主要介绍了C++动态规划之最长上升子序列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1 子序列与上升子序列

1.1 子序列

一个序列A={a1,a2,...an}中任意删除若干项,剩余的序列叫做A的一个子序列。例如序列A={1,3,5,4,2},删除其中的第3项和第5项,得到序列B={1,3,4},删除其中的第3项和第4项,得到序列C={1,3,2},此时序列B和C是序列A的子序列。

1.2 上升子序列

如果序列中的元素是从小到大排列的,则该序列为上升序列,如果该序列又是其它序列的子序列,则称为上升子序列。例如“1.1 子序列”中提到的B是A的上升子序列,而C是A的子序列,但不是上升子序列。

1.3 最长上升子序列

包含元素最多的上升子序列,叫做最长上升子序列。例如,序列D={1,5},是序列A的上升子序列,但不是最长上升子序列,而序列B是A的最长上升子序列。

2 动态规划求解最长上升子序列

2.1 流程

求解一个序列的最长上升子序列问题的流程如图1所示:

C++动态规划之最长上升子序列

图1 求解最长上升子序列流程

从图1中可以看出,在遍历素组中的元素时,如果该元素的值大于该元素之前的元素值时,就有可能构成上升子序列,此时需要找到之前元素对应的最长子序列的长度,找到这些长度的最大值,并且对该最大值加1,即为当前元素对应的最长子序列。从以上分析可知,动态规划求解最长上升子序列的“状态转移方程”为

dp(n) = max(dp(1),dp(2),...dp(n-1))+1

其中,n表示数组中元素的位置,即索引值。

2.2 核心代码

序列的最长上升子序列的核心代码如下所示:

for (int i = 1; i <= n; i++)
{
	dp[i] = 1;
	for (int j = 1; j <= i - 1; j++)
	{
		if (a[i] > a[j])
		{
			dp[i] = max(dp[i], dp[j]+1);
		}
	}
	length = max(length, dp[i]);
}

其中,第一个循环表示遍历数组中的所有元素;第二个循环表示遍历该元素之前的所有元素;第8行代码为“状态转移方程”;第11行代码的作用是找到数组中所有元素对应的最大值,即最长上升子序列的长度。

2.3 完整代码

序列的最长上升子序列的完整代码如下所示:文章来源地址https://www.toymoban.com/news/detail-413175.html

#include <iostream>
using namespace std;
 
int main()
{
	int a[10001] = { 0 };
	int dp[10001] = { 0 };
	int n;
	int length = 0;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
 
	for (int i = 1; i <= n; i++)
	{
		dp[i] = 1;
		for (int j = 1; j <= i - 1; j++)
		{
			if (a[i] > a[j])
			{
				dp[i] = max(dp[i], dp[j]+1);
			}
		}
		length = max(length, dp[i]);
	}
	cout<<(length);
	return 0;
}

到了这里,关于C++动态规划之最长上升子序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • AcWing 1.2.1 最长上升子序列模型 + 动态规划 + 图解(详细)

    (1)acwing 4557. 最长上升子序列  4557. 最长上升子序列 - AcWing题库 给定一个长度为 N 的整数序列  a1,a2,…,aN 。请你计算该序列的 最长上升子序列的长度 。上升子序列是指数值 严格单调递增的子序列 输入格式 第一行包含整数 N 第二行包含 N个整数 a1,a2,…,aN 输出格式 一行

    2024年02月06日
    浏览(38)
  • 动态规划系列 | 最长上升子序列模型(下)| 拦截导弹一网打尽!

    题目描述 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。 某天,雷达捕捉到敌国的导弹来袭。 由于该系统还在试用阶段,所以只有一套

    2024年02月03日
    浏览(49)
  • 最长上升子序列问题(LIS问题)与最长不上升子序列问题的四种方法(c++ 模板代码)

    最大上升子序列问题也叫做LIS问题,与最大公共子序列LCS问题是一类经典问题,在本章我们将总结一下求解 LIS最大上升子序列 的 几种方法 ,同时也会给出对应的 最大不上升子序列的求解方法。 关于LCS问题,我在后面会再出一篇博客来讲解, 废话不多说,我们直接进入正题

    2024年02月03日
    浏览(43)
  • 【C++】洛谷B3637 最长上升子序列

    这是一个简单的动规板子题。 给出一个由 n ( n ≤ 5000 ) n(nle 5000) n ( n ≤ 5000 ) 个不超过 1 0 6 10^6 1 0 6 的正整数组成的序列。请输出这个序列的 最长上升子序列 的长度。 最长上升子序列是指,从原序列中 按顺序 取出一些数字排在一起,这些数字是 逐渐增大 的。 第一行,一

    2024年02月19日
    浏览(32)
  • LeetCode | C++ 动态规划——300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

    300题目链接 dp 数组定义 dp[i] 表示 i 之前包括 i 的以 nums[i]结尾 的最长递增子序列的长度 需要包含nums[i]结尾,不然在做递增比较的时候,就没有意义了。 递推公式 位置 i 的最长递增子序列 等于 j 从 0 到 i - 1各个位置的最长递增子序列 + 1 的 最大值 if (nums[i] nums[j]) dp[i] = ma

    2024年02月16日
    浏览(46)
  • C++ 求解最长公共子序列(不仅仅求出其大小)(简单易懂!!!)(动态规划)

    求解两个数组的最长公共子序列我们需要用到的知识点有:动态规划dp,递归算法 先来说说动态规划dp 很多初学者在学习动态规划的时候总是百思不得其解,什么是动态规划呢,其实总结来说就是程序将计算过的结果记录下来,在下次使用到这条记录的时候不需要再次计算,

    2024年02月04日
    浏览(43)
  • C++ 动态规划经典案例解析之最长公共子序列(LCS)_窥探递归和动态规划的一致性

    动态规划处理字符相关案例中,求 最长公共子序列 以及求 最短编辑距离 ,算是经典中的经典案例。 讲解此类问题的算法在网上一抓应用一大把,即便如此,还是忍不住有写此文的想法。毕竟理解、看懂都不算是真正掌握,唯有瞧出其中玄机,能有自己独有的见解和不一样

    2024年02月13日
    浏览(37)
  • 上升子序列的最大长度,递归-记忆化搜索-动态规划三步走

    题目描述: 小明有一个数组,他想从数组任意元素开始向后遍历,找出所有上升子序列,并计算出最长的上升子序列的长度。 数据范围: 每组数据长度满足 1≤n≤200 1≤n≤200 , 数据大小满足 1≤val≤350 1≤val≤350 输入描述: 数据共2行,第1行先输入数组的个数,第2行再输

    2024年04月22日
    浏览(41)
  • (蓝桥杯第十一届决赛)试题D:本质上升序列(动态规划)

    先把题目中的字符串给出来:tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl 分析:虽然这只是一道填空题,但是我觉得这个还是有一定的思考意义的,所以我今天就把他

    2023年04月09日
    浏览(48)
  • 最长公共上升子序列(LCIS)

    目录 一、前言 二、最长公共上升子序列 1、问题描述 2、基本思路 (1)状态表示 (2)状态计算 三、题例 1、上链接 2、基本思路 3、代码 (1)python未优化版 (2)python优化版 对于学计算机的同学来说,学习算法是一件非常重要的事情,废话不多讲,我们来讲讲“最长公共上

    2023年04月09日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包