「动态规划」如何求最长递增子序列的长度?
300. 最长递增子序列
https://leetcode.cn/problems/longest-increasing-subsequence/description/
给你一个整数数组nums,找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。
- 输入:nums = [10,9,2,5,3,7,101,18],输出:4,解释:最长递增子序列是[2,3,7,101],因此长度为4。
- 输入:nums = [0,1,0,3,2,3],输出:4。
- 输入:nums = [7,7,7,7,7,7,7],输出:1。
提示:1 <= nums.length <= 2500,-10^4 <= nums[i] <= 10^4。
进阶:你能将算法的时间复杂度降低到O(nlog(n))吗?
我们用动态规划的思想来解决这个问题。
确定状态表示:根据经验和题目要求,我们用dp[i]表示:以i位置为结尾的所有子序列中,最长递增子序列的长度。
推导状态转移方程:以i位置为结尾的所有子序列分为2类:长度为1的子序列,长度大于1的子序列。如果子序列的长度是1,那么这个子序列是递增子序列。下面我们考虑长度大于1的子序列。
如果以i位置为结尾的子序列的长度大于1,我们可以继续细分为:i位置元素的前面是i - 1位置元素的子序列,i位置元素的前面是i - 2位置元素的子序列,i位置元素的前面是i - 3位置元素的子序列,……,i位置元素的前面是0位置元素的子序列。也就是说,如果子序列中,i位置元素的前面是j位置元素,那么j的范围是[0, i - 1]。
对于每一个j,如果nums[j] < nums[i],那么这个子序列就有可能是递增子序列。要想这个子序列尽可能得长,就要找到以j位置为结尾的最长递增子序列,在这个子序列后面添加nums[i],即为以i位置为结尾的最长递增子序列。
综上所述,dp[i]应该取:「1」和「所有满足0 <= j < i并且nums[j] < nums[i]的j中,最大的dp[j]加1」的较大值。
所以,我们可以把dp表的值都初始化为1,其中dp[0] = 1是显然的。如果i > 0,那么dp[i]就应该取:所有满足0 <= j < i并且nums[j] < nums[i]的j中,最大的dp[j]加1。
填表顺序:根据状态转移方程,显然应从左往右填表。
返回值:根据状态表示,应返回dp表的最大值。
细节问题:dp表的规模和nums相同,均为1 x n。
class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();// 创建dp表vector<int> dp(n, 1);// 填表for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp[i] = max(dp[i], dp[j] + 1);}}}return *max_element(dp.begin(), dp.end());}
};相关文章:
「动态规划」如何求最长递增子序列的长度?
300. 最长递增子序列https://leetcode.cn/problems/longest-increasing-subsequence/description/ 给你一个整数数组nums,找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其…...
深度神经网络DNN概念科普
深度神经网络DNN概念科普 深度神经网络(Deep Neural Network, DNN)是机器学习领域中一类具有多层结构的神经网络模型,它能够通过学习数据中的复杂模式来解决非线性问题。下面是对深度神经网络的详细解析: 基本组成部分 输入层&…...
Tomcat WEB站点部署
目录 1、使用war包部署web站点 2、自定义默认网站目录 3、部署开源站点(jspgou商城) 对主机192.168.226.22操作 对主机192.168.226.20操作 上线的代码有两种方式: 第一种方式是直接将程序目录放在webapps目录下面,这种方式…...
IPv6 中 MAC 33:33 的由来
一、33:33 由来 1. RFC9542 - 2024-05-02 Note IANA allocates addresses under the IANA OUI (00-00-5E) as explained in [RFC9542]. Unicast addresses under the IANA OUI start with 00-00-5E, while multicast addresses under the IANA OUI start with 01-00-5E. In t…...
告别手动邮件处理:使用imbox库轻松管理你的收件箱
imbox库简介: imbox是一个强大的Python库,专为与IMAP服务器交互而设计.IMAP(Internet Message Access Protocol)是一种用于电子邮件的标准协议,允许用户在远程服务器上管理邮件.imbox库通过IMAP协议与邮件服务器通信,帮助用户轻松地读取、搜索…...
Ubuntu 18.04 安装 PCL 1.14.1
在进行科研项目时,我们常常需要将 C 和 Python 结合起来编程。然而,每次将 PCL(Point Cloud Library)的内容添加到 CMakeLists.txt 文件中时都会报错。在深入分析后,我们推测可能是当前使用的 PCL 1.8 版本与现有程序不…...
公司logo设计大全怎么找?直接帮你设计logo
公司logo设计大全怎么找?在品牌塑造的过程中,Logo无疑是至关重要的一环。一个优秀的Logo不仅能够有效传达公司的核心理念和品牌形象,还能在消费者心中留下深刻的印象。然而,对于许多初创公司或小型企业来说,制作出适合…...
如何调整C#中数组的大小
前言 数组存储多个相同类型的一种非常常用的数据结构。它长度是固定,也就是数组一旦创建大小就固定了。C# 数组不支持动态长度。那在C#中是否有方法可以调整数组大小呢?本文将通过示例介绍一种调整一维数组大小的方法。 方法 数组实例是从 System.Arr…...
通过言语和非言语检索线索描绘睡眠中的记忆再激活茗创科技茗创科技
摘要 睡眠通过重新激活新形成的记忆痕迹来巩固记忆。研究睡眠中记忆再激活的一种方法是让睡眠中的大脑再次暴露于听觉检索线索(定向记忆再激活范式)。然而,记忆线索的声学特性在多大程度上影响定向记忆再激活的有效性,目前还没有得到充分探索。本研究通…...
MDPI旗下SSCI最新影响因子目录出炉!“水刊“Sustainability表现如何?
本周投稿推荐 SSCI • 1区,4.0-5.0(无需返修,提交可录) EI • 各领域沾边均可(2天录用) CNKI • 7天录用-检索(急录友好) SCI&EI • 4区生物医学类,0.1-0.5&…...
Matlab基础篇:数据输入输出
前言 数据输入和输出是 Matlab 数据分析和处理的核心部分。良好的数据输入输出能够提高工作效率,并确保数据处理的准确性。本文将详细介绍 Matlab 数据输入输出的各种方法,包括导入和导出数据、数据处理和数据可视化。 一、导入数据 Matlab 提供了多种方…...
MySQL字典数据库设计与实现 ---项目实战
软件准备✍:Mysql与Navicat可视化命令大全 ----项目实战 文章前言部分 目录 一.摘要 二.设计内容 三.项目实现 一.摘要 本项目关注于字典数据库表结构的设计和数据管理。通过现有的sql文件,实现system_dict_type和system_dict_data两个数据表。随后…...
python数据分析——数据预处理
数据预处理 前言一、查看数据数据表的基本信息查看info()示例 查看数据表的大小shape()示例 数据格式的查看type()dtype()dtypes()示例一示例二 查看具体的数据分布describe()示例 二…...
【Python】使用matplotlib绘制图形(曲线图、条形图、饼图等)
文章目录 一、什么是matplotlib二、matplotlib 支持的图形三、如何使用matplotlib1. 安装matplotlib2. 导入matplotlib.pyplot3. 准备数据4. 绘制图形5. 定制图形6. 显示或保存图形7. (可选)使用subplots创建多个子图注意事项: 四、常见图形使…...
vue下载本地xls模版静态文件
需求导入的下载模版不想放在服务器放在前端本地下载静态资源最简单的方式直接访问 public 文件夹下的文件 方法一:使用静态文件路径 将文件放在 public 文件夹中: 把你的文件从 src/assets 移动到 public 文件夹。例如:public/template.xls。…...
手机开热点,里面的WPA2-Personal和WPA3-Personal的区别
WPA2-Personal和WPA3-Personal这两种协议都是用来保护无线网络安全的,但它们在加密强度和安全性方面有所不同。 WPA2-Personal (Wi-Fi Protected Access 2) WPA2是目前最广泛使用的Wi-Fi安全标准之一。它使用AES(Advanced Encryption Standard…...
算法课程笔记——点积叉积
算法课程笔记——点积叉积...
详解 | DigiCert EV代码签名证书
简介 DigiCert EV 代码签名证书是一种高级别的代码签名证书,它不仅提供了标准代码签名证书的所有安全特性,还增加了额外的身份验证流程,以确保软件开发者或发布者的身份得到最严格验证。这对于提升软件的信任度、防止恶意篡改和确保下载安全…...
pdf压缩大小,PDF压缩大小不影响清晰度
你是否曾为PDF文件过大而烦恼?想要分享或上传文件时,却因为它的体积而束手无策?别担心,今天我将为大家分享一些简单实用的 PDF 压缩技巧,让你的文件轻松压缩pdf。 打开“轻云处理pdf官网”, 的网站。然后上…...
项目管理必备工具:2024年十大软件排行榜
有效的工具不仅可以帮助团队保持组织性,还能显著提高项目完成率。选择合适的项目管理软件,对于实现这些目标至关重要。 在2024年的各大权威榜单中,排名前十的项目管理软件包括:PingCode、Worktile(国内)&am…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
