动态规划-子序列问题1

文章目录

  • 1. 最长递增子序列(300)
  • 2. 摆动序列(376)
  • 3. 最长递增子序列的个数(673)
  • 4. 最长数对链(646)


1. 最长递增子序列(300)

题目描述:
在这里插入图片描述

状态表示:
根据经验以及题目要求,设置dp数组,dp[i]表示以i位置为结尾的子序列的最长长度。
状态转移方程:
这里因为涉及到序列的概念,要想获得dp[i]的值,首先需要遍历i位置之前的数组,如果数值小于i位置的数值,那么dp[i]的值就是该位置的dp数组值加一,最终dp[i]的值就是这些值中的最大值。状态转移方程可以归结为在nums[i]>nums[j]时,dp[i]=max(dp[i],dp[j]+1),这里的j取值是0到i-1,具体看代码。
初始化:
初始化直接将dp数组中的所有值都赋为1即可,因为以每个位置为结尾的递增子序列的长度是至少为1的。
填表顺序:
从左至右。
返回值:
返回dp数组最大值。
代码如下:

class Solution {public int lengthOfLIS(int[] nums) {int n = nums.length;int[] dp = new int[n];for (int i = 0; i < n; i++) {dp[i] = 1;}int max = dp[0];for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}max = Math.max(max, dp[i]);}return max;}
}

题目链接
时间复杂度:O(N^2)
空间复杂度:O(N)

2. 摆动序列(376)

题目描述:
在这里插入图片描述

动态表示:
设置两个数组f和g,分别代表i位置的数大于上一个位置的数值以及i位置的数值小于上一个位置的数值。
动态转移方程:
这里跟子数组问题中的最长湍流数组问题是一个道理,不过在搜索前一个数值的时候要加一个循环遍历i位置之前的数值,因为这里是序列问题,而不是数组问题。当i位置数值大于上一个数值时,f[i]=g[j]+1,当i位置数值小于上一个数值时,g[i]=f[j]+1。
初始化:
初始化的话,因为单个数值就可以构成长度为1的摆动序列,所以可以直接将f和g数组直接全部初始化1。
填表顺序:
从左至右。
返回值:
返回数组g和f中的最大值。
代码如下:

class Solution {public int wiggleMaxLength(int[] nums) {int n = nums.length;int[] f = new int[n];int[] g = new int[n];for (int i = 0; i < n; i++) {f[i] = 1;g[i] = 1;}int max = 1;for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {f[i] = Math.max(f[i], g[j] + 1);} else if (nums[i] < nums[j]) {g[i] = Math.max(g[i], f[j] + 1);}}max = Math.max(Math.max(g[i], f[i]), max);}return max;}
}

题目链接
时间复杂度:O(N^2)
空间复杂度:O(N)

3. 最长递增子序列的个数(673)

题目描述:
在这里插入图片描述

状态表示:
这题比较特殊,分别设置两个数组count[i]以及len[i]分别表示以i位置元素为结尾的子序列的最长严格递增子序列的个数以及最长严格递增子序列的长度。
状态转移方程:
因为题目是要求序列严格递增,所以只考虑在num[i]>nums[j]时的情况,在此时如果len[j]+1>len[i]时,len[i]=len[j]+1,并且将count[i]赋为count[j],如果len[j]+1==len[i],那么len数组的值不变,但是count[i]+=count[j]。这个过程如果结合前面子序列题目的思想是很好理解的,具体看代码。
初始化:
因为本题考虑的是递增子序列,单独的一个数值元素即可构成序列,所以可以直接将count和len数组的全部元素先赋为1。
填表顺序:
从左至右。
返回值:
返回以i位置为结尾的最长递增子序列的count数组中i位置的值,但是要考虑一种情况就是len数组中可能会出现多个相同的最大值,这样就要把count数组中的对应的多个位置的值加起来,这个过程可以使用一个简单的贪心算法解决。
代码如下:


class Solution {public int findNumberOfLIS(int[] nums) {int n = nums.length;int[] len = new int[n];int[] count = new int[n];for (int i = 0; i < n; i++) {len[i] = 1;count[i] = 1;}for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {if (len[i] < len[j] + 1) {count[i] = count[j];len[i] = len[j] + 1;} else if (len[i] == len[j] + 1) {count[i] += count[j];}}}}int ret = count[0];int max = len[0];for (int i = 1; i < n; i++) {if (max < len[i]) {ret = count[i];max = len[i];} else if (max == len[i]) {ret += count[i];}}return ret;}}

题目链接

时间复杂度:O(N^2)
空间复杂度:O(N)

4. 最长数对链(646)

题目描述:
在这里插入图片描述

状态表示:
根据经验以及题目要求设置一个数组dp,使用dp[i]来表示以第i个位置的数对作为结尾的最长数对链的长度。
状态转移方程:
这里的状态转移方程和这篇博客介绍的第一题的思路一致,都是在遍历pairs这个主数组时再加上一个循环,但是题目给出一个额外的条件就是可以无视顺序,所以为了得到更长的递增子序列要去提前将pairs数组给排序好,因为排序的是数对,所以在使用Arrays中的静态方法sort的时候要设置一个lambda表达式来指定排序的规则。
初始化:
还是一样,先对dp数组中的每一个元素都赋为1。
填表顺序:
从左至右。
返回值:
返回dp数组中的最大值即可。
代码如下:

class Solution {public int findLongestChain(int[][] pairs) {int n = pairs.length;Arrays.sort(pairs, (o1, o2) -> {return o1[0] - o2[0];});int[] dp = new int[n];for (int i = 0; i < n; i++) {dp[i] = 1;}int max = dp[0];for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (pairs[i][0] > pairs[j][1]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}max = Math.max(max, dp[i]);}return max;}}

题目链接

时间复杂度:O(N^2)
空间复杂度:O(N)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1410869.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

38.基础乐理-其余调号说明

目前只写了自然大调&#xff0c;还有其它的调式没有写&#xff0c;大调中还有 和声大调 与 旋律大调&#xff0c;除了大调&#xff0c;还有小调式、五声调式、中古调式等还有很多很多&#xff0c;这些东西是需要对于调号、拍号&#xff0c;对于五线谱、对于音程和弦都有一定程度…

OS考研chapter3内存管理

目录 一、基础知识点补充 1.内存、内存地址概念与联系 2.按byte编址 vs 按字编码 二、进程运行的基本原理 1.指令的工作原理 2.逻辑地址 vs 物理地址 3.从写程序到程序运行 &#xff08;1&#xff09;编辑源代码 &#xff08;2&#xff09;编译 &#xff08;3&#xf…

JZ69跳台阶

&#x1f600;前言 青蛙跳台阶是一个经典的问题&#xff0c;它描述了一只青蛙每次可以跳上1级台阶或者2级台阶&#xff0c;问跳上一个n级的台阶有多少种跳法。这个问题看似简单&#xff0c;实则蕴含了一定的数学思维和递推关系。在本文中&#xff0c;我们将通过分析问题的特性和…

合并两个有序数组(详解)

合并两个有序数组&#xff08;详解&#xff09; 合并两个有序数组 题目&#xff1a; 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2&#xff0c;另有两个整数 m 和 n &#xff0c;分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中&#xff0c;…

空闲缓冲区(empty) 和 非空缓冲区(full) 的的概念和区别【操作系统 生产者——消费者进程】

首先&#xff0c;我们得有个环境——通常是个缓冲池&#xff0c;这个池子里可以塞很多缓冲区&#xff0c;它们是用来存放数据的。生产者就是那个不停造东西的家伙&#xff0c;而消费者则是等着用这些东西的人。 1. 空闲缓冲区&#xff08;empty&#xff09;&#xff1a; 这玩意…

顺序表经典算法

顺序表经典算法 1.移除元素 题目&#xff1a; 给你一个数组 nums 和一个值 val&#xff0c;你需要 原地 移除所有数值等于 val 的元素&#xff0c;并返回移除后数组的新长度。 不要使用额外的数组空间&#xff0c;你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的…

Linux编辑器调试器 gcc/g++ gdb 编译过程及使用讲解

这恋爱呀 我有两不谈 第一异性不谈 因为我们性别不一样 我知道的她不知道相处起来太累 第二同性不谈 因为我们性别一样 我知道的他也知道相处起来太无聊了 –❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–…

雅思(IELTS)优秀小作文分享

IELTS优秀小作文分享 柱状图 本篇范文个人评分是8分或者8.5分&#xff0c;属于能找到的最优质的范文了 题目如下: The two sets of bar charts illustrate the amount of time that teenagers (boys, girls, and all) in the UK spend chatting online and playing game c…

DHCPv4_CLIENT_ALLOCATING_01: 在其本地物理子网上广播DHCPDISCOVER消息

测试目的&#xff1a; 确保客户端能够在其本地物理子网上广播DHCPDISCOVER消息。 描述&#xff1a; 该测试用例旨在验证DHCP客户端是否能够正确地在其本地物理子网上广播DHCPDISCOVER消息&#xff0c;以便进行IP地址的自动分配。 测试拓扑&#xff1a; 测试步骤&#xff1a…

汇报进度26届cpp,目前来说之后的规划,暑假打算回家10天就留校沉淀了

汇报一下进度吧&#xff0c;26双非菜鸡&#xff0c;cpper. 但目前学了一些go &#xff0c;辅修吧&#xff0c;距离发的上个动态已经过去3个月了&#xff0c;真的觉得找实习时间来不及&#xff0c;现在leetcode 100多道题&#xff0c;前几天蓝桥杯整了个省二&#xff0c;把OS和…

利用大语言模型(KIMI)构建智能产品的控制信息模型

数字化的核心是数字化建模&#xff0c;为一个事物构建数字模型是一项十分复杂的工作。不同的应用场景&#xff0c;对事物的关注重点的不同的。例如&#xff0c;对于一个智能传感器而言&#xff0c;从商业的角度看&#xff0c;产品的信息模型中应该包括产品的类型&#xff0c;名…

Linux蛋疼笔记之无法安装软件

Ubuntu在安装软件时&#xff0c;一直安装失败&#xff0c;提示&#xff1a; dpkg: error processing package gconf2-common (--configre):installed gconf2-common package post-installation script susprocess returned error exit status 10 Error wre encountered while …

数字滤波器设计笔记1

系统结构 1.先利用matlab的simulink和FDA进行滤波器建模设计&#xff0c;通过仿真后&#xff0c;确定模型达到相应的性能要求&#xff0c;再利用verilog进行电路设计。最后使用modelsim进行功能验证。其中testbench的输入数据&#xff0c;利用matlab模型的输入数据。 2.Matlab…

基于openwrt和libssh2实现ssh的远程登录

libssh2的支持 openwrt本身带有libssh和libssh2两种三方库。我们需要修改编译使其参与编译./scripts/feeds update -a ./scripts/feeds install -a执行make menuconfig操作&#xff0c;勾选你想要的三方库 ssh服务器的连接 这里需要注意的主要就是makefile里面记得添加ssh2…

刷代码随想录有感(52):用数组最大值及其两侧构造最大二叉树

题干&#xff1a; 代码&#xff1a; class Solution { public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if(nums.size() 1)return new TreeNode(nums[0]);int maxvalue INT_MIN;int maxindex;for(int i 0; i < nums.size(); i){if(nums[i] …

[C++][数据结构]红黑树的介绍和模拟实现

前言 之前我们简单学习了一下搜索树和平衡搜索树&#xff0c;今天我们来学习一下红黑树 简介 概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存储位表示结点的颜色&#xff0c;可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着…

地图产业的困局与破局:高精地图“上车”难 轻量化渐成主流方案 | 最新快讯

《科创板日报》5月3日讯&#xff08;编辑 邱思雨&#xff09; 近期&#xff0c;特斯拉与百度的“绯闻”成为智驾、地图行业的焦点。 有媒体消息称&#xff0c;特斯拉将与百度地图独家深度定制车道级高辅地图。《科创板日报》记者也获悉&#xff0c;自5月1日起&#xff0c;百度…

pygame鼠标绘制

pygame鼠标绘制 Pygame鼠标绘制效果代码 Pygame Pygame是一个开源的Python库&#xff0c;专为电子游戏开发而设计。它建立在SDL&#xff08;Simple DirectMedia Layer&#xff09;的基础上&#xff0c;允许开发者使用Python这种高级语言来实时开发电子游戏&#xff0c;而无需被…

ESXi8 中FreeBSD启动失败记录

一天突然发现ESXi8 中的FreeBSD启动失败&#xff0c;且自动挂载了FreeBSD的安装光盘&#xff0c;进入安装步骤。 惊了一身冷汗。 到虚拟主机设置里&#xff0c;发现引导选项里面&#xff0c;选择应当用来引导虚拟机的固件为EFI&#xff0c;原来是前段时间手残修改了&#xff0…

图片倾斜矫正处理(Hough Transform)

目录 倾斜矫正原理及实现方式Canny边缘检测非极大值抑制霍夫变换 倾斜矫正原理及实现方式 代码连接&#xff1a;https://github.com/shuyeah2356/Image-Angel-correction/tree/main 倾斜矫正的实现原理&#xff1a; 使用霍夫变换检测图片中的直线&#xff1b; 计算直线与水平方…