每天一道leetcode:300. 最长递增子序列(动态规划中等)
今日份题目:
给你一个整数数组 nums
,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]
是数组 [0,3,1,6,2,2,7]
的子序列。
示例1
输入:nums = [10,9,2,5,3,7,101,18] 输出:4 解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
示例2
输入:nums = [0,1,0,3,2,3] 输出:4
示例3
输入:nums = [7,7,7,7,7,7,7] 输出:1
提示
-
1 <= nums.length <= 2500
-
-104 <= nums[i] <= 104
题目思路
动态规划的精髓,我认为,就是站在当前位置做出判断进而得出结果。
本题中,使用一维dp数组记录到目前为止,满足要求的递增序列的最大长度。那么站在当前位置,需要进行的判断是,如果前边没有比我小的,那么我会为1,否则我应该是最长的那个递增序列的长度加一。故得到状态转移方程:dp[i]=max(dp[i],dp[j]+1);
代码
class Solution
{
public:int lengthOfLIS(vector<int>& nums) {if(nums.size()==0) return 0;int maxn=0;int dp[3000]={0};dp[0]=1;maxn=1;int temp=0;for(int i=1;i<nums.size();i++){dp[i]=1;for(int j=0;j<i;j++){if(nums[j]<nums[i]) {dp[i]=max(dp[i],dp[j]+1);} }}int res=0;for(int i=0;i<nums.size();i++){res=max(res,dp[i]);}return res;}
};
提交结果
欢迎大家在评论区讨论,如有不懂的代码部分,欢迎在评论区留言!
相关文章:

每天一道leetcode:300. 最长递增子序列(动态规划中等)
今日份题目: 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] …...

【无监督】2、MAE | 自监督模型提取的图像特征也很能打!(CVPR2022 Oral)
文章目录 一、背景二、方法三、效果 论文:Masked Autoencoders Are Scalable Vision Learners 代码:https://github.com/facebookresearch/mae 出处:CVPR2022 Oral | 何凯明 | FAIR 一、背景 本文的标题突出了两个词: masked…...

pytorch单机多卡后台运行
nohup sh ./train_chat.sh > train_chat20230814.log 2>1&参考资料 Pytorch单机多卡后台运行的解决办法...

linux配置上网 linux adsl拨号上网设置
Linux里面配置ADSL上网是件很麻烦的事。但配置完成之后就能开机自动拨号上网,可谓十分的方便。支持的系统有Redhat,CentOS,SuSE,FreeBSD,Ubuntu等常见的Linux。 工具/原料 ADSL网络,电信,网通,移动等常见宽带。 Linux系统的安装光…...
XML学习基础知识归纳(一)
一、XML基本概述 (1)概念:XML是可扩展的标记语言,xml文档的后缀名为 .xml (2)作用:用来用来传输和存储数据,不用于表现和展示数据,这点呢相比于HTML来说是不同的&#…...

2023.8.14论文阅读
文章目录 ESPNet: Efficient Spatial Pyramid of Dilated Convolutions for Semantic Segmentation摘要本文方法实验结果 DeepFusion: Lidar-Camera Deep Fusion for Multi-Modal 3D Object Detection摘要本文方法实验结果 ESPNet: Efficient Spatial Pyramid of Dilated Convo…...

FL Studio for Windows-21.1.0.3713中文直装版功能介绍及系统配置要求
FL Studio 21简称FL水果软件,全称是:Fruity Loops Studio编曲,由于其Logo长的比较像一款水果因此,在大家更多的是喜欢称他为水果萝卜,FL studio21是目前最新的版本,这是一款可以让你的计算机就像是一个全功能的录音室&…...
基于网格变形的二维图像变形算法:C++实现与应用
在计算机图形学中,图像变形是一种常见的技术,它可以改变图像的形状和结构,以满足特定的视觉效果或者应用需求。本文将介绍一种基于网格变形的二维图像变形算法,并使用C进行实现。 一、算法原理 网格变形是一种基于网格的图像变形…...

【数据结构】八大排序详解
🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🐌 个人主页:蜗牛牛啊 🔥 系列专栏:🛹数据结构、🛴C 📕 学习格言:博观而约取&…...

VSCode如何设置高亮
一、概述 本文主要介绍在 VSCode 看代码时,怎样使某个单词高亮显示,主要通过以下三步实现: 安装 highlight-words 插件 配置 highlight-words 插件 设置高亮快捷键F8 工作是嵌入式开发的,代码主要是C/C的,之前一直用…...
密钥大全ubuntu
VMware Workstation Tech Preview 20H2 GG1JR-APD1P-0857Q-DQQN9-PU2CA VMware Workstation v16 Pro for Windows(反馈失效) ZF3R0-FHED2-M80TY-8QYGC-NPKYF YF390-0HF8P-M81RQ-2DXQE-M2UT6 ZF71R-DMX85-08DQY-8YMNC-PPHV8 VMware Workstation v15 f…...

Spring Task入门案例
Spring Task 是Spring框架提供的任务调度工具,可以按照约定的时间自动执行某个代码逻辑。 定位:定时任务框架 作用:定时自动执行某段Java代码 强调:只要是需要定时处理的场景都可以使用Spring Task 1. cron表达式 cron表达式…...

针对Android项目蓝牙如何学习
一、概述(Overview) 蓝牙是一种专有的开放式无线技术标准,用于在固定和移动设备之间进行短距离数据交换(使用2400–2480 MHz ISM波段的短波长无线电传输),从而创建具有高度安全性的个人局域网(PANs)。由电信供应商爱立信(telecoms vendor Ericsson)于1994年创建,[1…...
C++学习笔记总结练习:内存分配器编程实现
内存分配器练习 C内存分配器是用于管理程序运行时内存的工具。它负责分配和释放内存,以满足程序在运行过程中的动态内存需求。在C中,有几种内存分配器可供选择,包括操作系统提供的默认分配器、自定义分配器和第三方库提供的分配器。 默认分配…...

【uniapp】使用Vs Code开发uniapp:
文章目录 一、使用命令行创建uniapp项目:二、安装插件与配置:三、编译和运行:四、修改pinia: 一、使用命令行创建uniapp项目: 二、安装插件与配置: 三、编译和运行: 该项目下的dist》dev》mp-weixin文件导入微信开发者…...

【STM32】高效开发工具CubeMonitor快速上手
工欲善其事必先利其器。拥有一个辅助测试工具,能极大提高开发项目的效率。STM32CubeMonitor系列工具能够实时读取和呈现其变量,从而在运行时帮助微调和诊断STM32应用,类似于一个简单的示波器。它是一款基于流程的图形化编程工具,类…...
React 使用 i18n 翻译换行解决方法
当前问题: json 配置文件 "detail": {"10001": "Top 10 \nBIGGEST WINS" } 按以上方式文本在渲染的时候并不能识别我们加入 \n 要实现换行的意图,通过拆分成两个多语来实现又太低级。 解决方法: 在该多语…...

QEMU源码全解析37 —— Machine(7)
接前一篇文章:QEMU源码全解析36 —— Machine(6) 本文内容参考: 《趣谈Linux操作系统》 —— 刘超,极客时间 《QEMU/KVM》源码解析与应用 —— 李强,机械工业出版社 特此致谢! 上回书讲完了q…...

如何将阿里云WiredTiger引擎的MongoDB物理备份文件恢复至自建数据库
数据库操作一直是一个比较敏感的话题,动不动“删库跑路”,可见数据库操作对于一个项目而言是非常重要的,我们有时候会因为一个游戏的严重bug或者运营故障要回档数据库,而你们刚好使用的是阿里云的Mongodb,那么这篇文章…...
SAP FIORI Launchpad 403 forbidden error
问题: 在前台输入/N/UI2/FLP 浏览器显示 403 forbidden 查阅资料得知 相关sicf 的服务未激活 note:3011106 检查以下所有服务是否已在事务代码 SICF 中激活: /default_host/sap/bc/ui2/nwbc/ /default_host/sap/bc/ui2/start_up /default_host/sap…...

深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...