动态规划-子序列问题1

embedded/2024/9/23 14:35:46/

文章目录

  • 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.ppmy.cn/embedded/23767.html

相关文章

CSS接触

标签&#xff1a; 块标签&#xff0c;用来给网页分块 默认占一行<div></div> 无意义标签 <span></span> 背景颜色 background-color:颜色 字体颜色color: 颜色; 使用css&#xff1a; 一、使用css- 内嵌样式&#xff1a; 1. 在h…

stringRedisTemplate.opsForValue().increment(key)报空指针异常

解决办法&#xff1a;https://www.jianshu.com/p/789b33b5943e BUG复现满足以下条件可触发&#xff1a; 1.在RedisConfig开启Redis事务 redisTemplate.setEnableTransactionSupport(true);2.业务中开启事务 Transactional3.同一个业务下用生产多点id就报这个错误了 Cannot in…

Git变更账户、查看账户

1、变更账户 &#xff08;1&#xff09;修改当前文件夹用户 git config user.name “新用户名” git config user.email “新邮箱” &#xff08;2&#xff09;修改全局git用户 git config - -global user.name “新用户名” git config - -global user.email “新邮箱”…

银河麒麟V10 ARM64 离线安装 新版Docker

查询当前发行版本 nkvers下载最新版本 卸载旧依赖 卸载已经安装的老版本 yum remove docker \containerd.io \docker-runc \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-engine \docker-compo…

前端科举八股文-HTML篇

前端面试-HTML篇 什么是http?http和https有什么区别https的加密过程?http2.0有什么改进?src和href的区别对html语义化标签的理解?script标签中defer和asyc的区别?举出几个常见的行内、块级元素什么是webworker&#xff1f;iframe的优缺点&#xff1f;介绍一下tcp三次握手f…

2024LarkXR新增功能系列之五 | 单端口支持多并发

实时云渲染技术在为虚拟现实、游戏、和各种应用程序提供强大的渲染支持的同时&#xff0c;也带来了一些网络和运维上的挑战。在传统的设置中&#xff0c;实时云渲染推流技术需要为每个视频流单独占用服务器的一个端口。这种方法在多用户同时访问的情况下可能会导致端口资源的快…

开源博客项目Blog .NET Core源码学习(18:App.Hosting项目结构分析-6)

本文学习并分析App.Hosting项目中后台管理页面的_AminLayout.cshtml模版页面和登录页面。 _AminLayout.cshtml模版页面 后台管理页面中的大部分页面都使用_AminLayout.cshtml作为模板页面&#xff0c;如下图所示&#xff0c;后台页面的视图内容放置在表单中&#xff0c;使用la…

photoshop如何使用PS中的吸管工具吸取软件外部的颜色?

第一步&#xff0c;打开PS&#xff0c;随意新建一个画布&#xff0c;或打开一个图片。 第二步&#xff0c;将PS窗口缩小&#xff0c;和外部窗口叠加放置&#xff0c;以露出后面的其它页面。 第三步&#xff0c;选中吸管工具&#xff0c;在PS窗口内单击一点吸取颜色&#xff0c;…