【动态规划】子序列问题(上)

1. 最长递增子序列

300. 最长递增子序列

和子数组不同的是,子数组要求是连续的,子序列只要下标是递增的就可以,这里严格递增的意思是不能有相等的元素,必须一直递增

状态表示:以 i 位置为结尾的所有的子序列中最长递增子序列的长度

状态转移方程:

当枚举到 i 位置时,如果是单个 i 构成的子序列那么 dp[i] 就是 1,如果子序列长度大于 1,就是在 0 ~ j ( 0<= j < i)区间内找出一个最长的递增子序列,并且只有在 nums[j] > nums[i] 的时候才能把 d[i] 更新为 dp[j] + 1,由于在 0 ~ j 区间内任意位置都可能有一个最长的递增子序列,所以更新 dp[i] 的时候需要取它们的最大值

初始化:可以吧 dp 表中的元素全部初始化为 1,也就是最差情况都是 1

填表顺序:从左到右

返回值:dp 数组中的最大值

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

2. 摆动序列

376. 摆动序列

状态表示:由于这道题有上升和下降两种状态,所以可以定义两个状态表示

f[i] :以 i 位置为结尾的所有子序列中,最后一个状态处于上升状态的最长摆动子序列的长度

g[i] :以 i 位置为结尾的所有子序列中,最后一个状态处于下降状态的最长摆动子序列的长度

状态表示:

和上一题类似,只不过分为两种情况,当 num[j] < num[i] 时,也就是准备上升的状态,此时 f[i] 就是从 g[j] + 1 中取一个最大值,当 num[j] > num[i] 时,也就是准备下降的状态,此时 g[i] 就是从 f[j] + 1 中取一个最大值

初始化:还是可以把两个 dp 表都初始化为 1

返回值:两个 dp 表中的最大值

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] = g[i] = 1;}int ret = 1;for(int i = 1;i < n;i++){for(int j = 0;j < i;j++){if(nums[i] > nums[j]){f[i] = Math.max(g[j] + 1,f[i]);}if(nums[i] < nums[j]){g[i] = Math.max(f[j] + 1,g[i]);}}ret = Math.max(g[i],ret);ret = Math.max(f[i],ret);}return ret;}
}

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

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

状态表示:

dp[i] 还是像之前一样存储以 i 结尾最长递增子序列的长度,还需要统计个数,所以还需要再定义一个状态来表示以 i 结尾时最长递增子序列的个数

状态转移方程:

求最长递增子序列的长度是和之前一样的,求个数的时候由于以 i 结尾时可能会有多个递增子序列的长度是一样的,所以就需要把这些情况都加起来,由于求的是最长的子序列,在开始从左往右遍历的时候还不能确定整个数组中的最长递增子序列长度,但是可以知道以当前位置结尾时的最长长度,当后续再遇到更长的子序列,就需要把 count 表里的重新更新,遇到一样的话就相加

两个表都初始化完之后再按照上面的方法遍历一遍求出最长递增子序列的个数即可

class Solution {public int findNumberOfLIS(int[] nums) {int n = nums.length;int[] dp = new int[n];int[] count = new int[n];for(int i = 0;i < n;i++){dp[i] = count[i] = 1;}for(int i = 1;i < n;i++){for(int j = 0;j < i;j++){if(nums[i] > nums[j]){//长度一样if(dp[i] == dp[j] + 1){count[i] += count[j];}//找到了更长的子序列if(dp[i] < dp[j] + 1){count[i] = count[j];dp[i] = dp[j] + 1;}}}}int ans = 0,ret = 1;for(int i = 0;i < n;i++){if(ret < dp[i]){ret = dp[i];ans = count[i];}else if(ret == dp[i]){ans += count[i];}}return ans;}
}

4. 最长数对链

646. 最长数对链

使用动态规划时需要确定之前的状态,但是这道题如果直接进行表示的话,下一个位置选在哪里是不能确定的,所以需要提前排好顺序,然后就变成了最长递增子序列的问题,此时只要 pairs[i][0] 的元素大于上一个 pairs[j][1],就可以连在上一个状态上了

class Solution {public int findLongestChain(int[][] pairs) {Arrays.sort(pairs,(a,b)->a[0] - b[0]);int n = pairs.length;int[] dp = new int[n];Arrays.fill(dp,1);int ret = 1;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);}}ret = Math.max(ret,dp[i]);}return ret;}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Android GPU Inspector分析帧数据快速入门

使用 谷歌官方工具Android GPU Inspector (AGI) 可以对Android 应用进行深入和全面的系统性能分析和帧性能分析 。AGI 是一个非常强大的分析工具&#xff0c;尤其是在需要诊断 GPU 性能问题和优化应用时&#xff0c;可以帮助你精准找到性能瓶颈。本文介绍如何使用该工具对帧数据…

梳理一下spring中,与message相关的知识点

本次梳理的相关知识点包括jms&#xff0c;amqp(rabbitmq)&#xff0c;sping-messaging&#xff0c;spring-integration&#xff0c;springcloud-stream&#xff0c;这些都是与消息message相关的内容&#xff0c;它们有什么区别与联系呢&#xff1f; 相关的要点与相互关系都整理…

物联网消息队列Emqx日志配置及日志追踪以及Centos7上的rc.local开机不执行、git提交的小问题

一、物联网消息队列Emqx日志配置及日志追踪 EMQX支持将日志输出到控制台或者日志文件&#xff0c;或者同时使用两者。使用 Docker 部署 EMQX&#xff0c;默认只能通过 docker logs 命令查看 EMQX 日志。EMQX 的默认日志级别为 warning&#xff0c;默认在单日志文件超过10MB(log…

word压缩大小怎么弄?快来试试这几种压缩word方法!

word压缩大小怎么弄&#xff1f;在处理Word文档时&#xff0c;如果遇到体积过大的情况&#xff0c;无疑会带来一系列麻烦&#xff0c;大型Word文档不仅占据大量存储空间&#xff0c;而且在传输过程中会耗费更多时间&#xff0c;想象一下&#xff0c;当你急需将一份重要的文档发…

Perl打印9x9乘法口诀

本章教程主要介绍如何用Perl打印9x9乘法口诀。 一、程序代码 1、写法① use strict; # 启用严格模式&#xff0c;帮助捕捉变量声明等错误 use warnings; # 启用警告&#xff0c;帮助发现潜在问题# 遍历 1 到 9 的数字 for my $i (1..9) {# 对于每个 $i&#xff0c;遍历 1…

【设计模式系列】观察者模式

一、什么是观察者模式 观察者模式&#xff08;Observer Pattern&#xff09;是一种行为设计模式&#xff0c;它定义了对象之间的一对多依赖关系&#xff0c;当一个对象的状态发生变化时&#xff0c;所有依赖于它的对象都会得到通知并自动更新。这种模式也被称为发布-订阅模式&…

【AscendC算子开发】笔记2 算子高级开发和调试调优

算子调试 Tensor也可以通过特定的printf方法来打印&#xff0c;见上图。 gdb调试见上图。 为什么gdb调试无法成功&#xff0c;因为run.sh里面有两行export&#xff0c;如果直接通过.XX运行的话需要配置一下。 npu域也支持调试&#xff0c;可以使用上述的方法。 内存检测工…

AI自动生成PPT哪个软件好?智能生成PPT不再熬夜做课件

大概这世上&#xff0c;都是职场牛马对“PPT”这三个字母的头痛反应最大吧&#xff01; 是的&#xff0c;就连各个年级段的老师也是很头痛——愁着怎样能在排版整齐的情况下&#xff0c;将必考知识点都呈现在PPT每一张幻灯片页面里...... 近期打听到用人工智能生成ppt课件&am…

ProtoBuf 的含义和安装

ProtoBuf 是什么 Protocol Buffers 是 Google 的⼀种语⾔⽆关、平台⽆关、可扩展的序列化结构数据的⽅法&#xff0c;它可⽤ 于&#xff08;数据&#xff09;通信协议、数据存储等。 Protocol Buffers 类⽐于、 XML&#xff0c;是⼀种灵活&#xff0c;⾼效&#xff0c;⾃动化机…

Java项目-基于springboot框架的智慧外贸系统项目实战(附源码+文档)

作者&#xff1a;计算机学长阿伟 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、ElementUI等&#xff0c;“文末源码”。 开发运行环境 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringBoot、Vue、Mybaits Plus、ELementUI工具&#xff1a;IDEA/…

2024年最新苹果iOS证书申请创建App详细图文流程

iOS 证书设置指南&#xff1a; 对于开发者来说&#xff0c;在没有Mac电脑或对Xcode等开发工具不熟悉的情况下&#xff0c;如何快速完成IOS证书制作和IPA文件提交至开发者中心一直是一个难题。但是现在&#xff0c;有了初雪云提供的极简工具&#xff0c;您可以轻松实现这两个任…

Tomcat隐藏版本号和报错信息

为了避免漏洞扫描的时候造成版本泄露&#xff0c;可以在conf/server.xml配置文件中的<Host>配置项中添加如下配置: <Valve className"org.apache.catalina.valves.ErrorReportValve" showReport"false" showServerInfo"false" /> …

c语言内核链表

c语言内核链表 在Linux中拥有大量的内核源码&#xff0c;在数据存储的这块位置拥有内核链表&#xff08;双向循环链表&#xff09; 由linux内核提供的链表文件&#xff0c;里面包含了多组内联函数和宏定义函数以及功能性函数。 内核链表中定义了多个函数&#xff0c;我们只需要…

(gersemi) CMake 格式化工具

文章目录 &#x1f9ee;介绍&#x1f9ee;安装&#x1f9ee;使用&#x1f5f3;️模式 modes&#x1f5f3;️样式配置 config ⭐END&#x1f31f;help&#x1f31f;交流方式 &#x1f9ee;介绍 BlankSpruce/gersemi: A formatter to make your CMake code the real treasure A f…

关闭或开启Win11系统的自动更新

Win11系统老是自动更新&#xff0c;每次更新后不仅拖慢计算机的运行速度&#xff0c;甚至打印机都无法使用了&#xff0c;给我们带来了很多困扰。 那么我们该如何彻底关闭Win11系统的自动更新呢&#xff1f;关闭Win11系统自动更新会有什么弊端呢&#xff1f; 下面就分享几个小方…

NVIDIA 发布适用于网络安全的 NIM Blueprint

德勤使用适用于容器安全的 NVIDIA NIM Agent Blueprint 帮助企业利用开源软件构建安全的 AI。 文章目录 &#x1f64a; 德勤使用 NVIDIA AI 保障软件安全&#x1f64a; 通过生成式 AI 保障软件安全&#x1f64a; 适用于网络安全成功的蓝图&#x1f3a0; 什么是 NVIDIA NIM Agen…

ESP32移植Openharmony外设篇(3)OLED屏

模块简介 产品介绍 OLED (Organic Light-Emitting Diode)&#xff1a;有机发光二极管又称为有机电激光显示&#xff0c;OLED显示技术具有自发光的特性&#xff0c;采用薄的有机材料涂层和玻璃基板&#xff0c;当有电流通过时&#xff0c;这些有机材料就会发光&#xff0c;而且…

数组中的算法

目录 1.什么是数组 2.数组上的算法 2.1二分查找算法 什么是二分查找算法&#xff1f; 算法步骤 算法时间复杂度 一个问题 例题 题目分析 解题代码 2.2双指针法 什么是双指针法&#xff1f; 例题 题目分析 解题代码 1.什么是数组 数组是在一块连续的内存空间…

【vuejs】富文本框输入的字符串按规则解析填充表单

今天遇到一个批量添加信息的需求&#xff0c;按照格式要求解析后填充到表单中&#xff0c;不符合规则的直接过滤掉 注&#xff1a;添加的信息都是随机生成&#xff0c;不用于实际用途 这是弹框输入的文本解析代码 export const editValToArr (value, bankArr) > {return n…

vue2-render:vue2项目使用render / 基础使用

一、本文内容 本文内容记录render常用的一些属性和方法的配置&#xff0c;以作参考 export default { data() {return { modelValue: ,key: 0,}; }, render(h) { return h(div, [ h(input, {class: input,attrs: { type: text }, key: this.key,props: { value: thi…