当前位置: 首页 > news >正文

leetcode300. 最长递增子序列,动态规划附状态转移方程

leetcode300. 最长递增子序列

给你一个整数数组 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

在这里插入图片描述

目录

  • leetcode300. 最长递增子序列
  • 子序列与子串的区别
    • 子序列(Subsequence)
    • 子串(Substring)
    • 总结
  • 最长递增子序列问题
    • 题目描述
    • 题目分析
    • 算法
    • 状态转移方程
      • 初始化
      • 遍历进行状态转移
      • 返回结果
    • 算法流程
    • 代码实现
    • 打表过程
    • 最终结果
    • 算法分析
    • 易错点
    • 相似题目

子序列与子串的区别

子序列(Subsequence)

  • 定义:一个给定序列的子序列是从原序列中在不改变序列顺序的情况下删除某些元素(也可以不删除任何元素)而形成的序列。
  • 特点
    • 不需要连续。
    • 保持元素的原有顺序。
  • 示例:对于序列 A = [5, 1, 22, 25, 6, -1, 8, 10][5, 22, 25][1, 6, -1] 都是它的子序列。

子串(Substring)

  • 定义:子串是指从原字符串中连续取出的一部分。
  • 特点
    • 必须连续。
    • 保持元素的原有顺序。
  • 示例:对于字符串 S = "abcdefg""abc""def" 都是它的子串。

总结

  • 主要区别:子序列不要求连续,而子串必须是连续的。

最长递增子序列问题

题目描述

给定一个整数数组,找到最长的递增子序列的长度。

题目分析

这是一个经典的动态规划问题。我们可以通过计算以每个元素为结尾的最长递增子序列的长度来最终得到整个数组的最大递增子序列长度。

算法

状态转移方程

  • 定义dp[i] 表示以 nums[i] 为结尾的最长递增子序列的长度。
  • 转移方程dp[i] = max(dp[i], dp[j] + 1),其中 0 <= j < inums[i] > nums[j]
  • 解释
    • 如果 nums[i] 大于 nums[j],那么 nums[i] 可以加到以 nums[j] 结尾的递增子序列的末尾,形成一个新的更长递增子序列。
    • 因此,我们需要更新以 nums[i] 结尾的最长递增子序列的长度。
    • max(dp[i], dp[j] + 1) 确保了对于每个 nums[i],我们选择一个最优的 dp[j] 来形成新的递增子序列。

初始化

  • dp[i] = 1,因为任何单个元素自身都是一个递增子序列。

遍历进行状态转移

  • 遍历数组,对于每个元素 nums[i],再遍历其之前的所有元素 nums[j],如果 nums[i] > nums[j],则更新 dp[i]

返回结果

  • 返回 dp 数组中的最大值,即为最长递增子序列的长度。

算法流程

开始
初始化dp数组
遍历i从1到n-1
遍历j从0到i-1
更新dp i
更新结果
结束

代码实现

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();if (n == 1) return 1;int result = 0;vector<int> dp(n, 1);for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = max(dp[j] + 1, dp[i]);}}result = max(result, dp[i]);}return result;}
};

打表过程

在这里插入图片描述

最终结果

  • 最长递增子序列长度为 4,对应于 dp[7]

算法分析

  • 时间复杂度:O(n^2),因为我们需要遍历数组中的每个元素,对于每个元素,我们又需要遍历其之前的所有元素。
  • 空间复杂度:O(n),用于存储 DP 数组。

易错点

  • 注意在遍历时正确应用状态转移方程。
  • 确保在更新 dp[i] 时考虑所有可能的 dp[j]

相似题目

题目链接
最长连续递增序列LeetCode 674
俄罗斯套娃信封问题LeetCode 354
最长公共子序列LeetCode 1143

相关文章:

leetcode300. 最长递增子序列,动态规划附状态转移方程

leetcode300. 最长递增子序列 给你一个整数数组 nums &#xff0c;找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列&#xff0c;删除&#xff08;或不删除&#xff09;数组中的元素而不改变其余元素的顺序。例如&#xff0c;[3,6,2,7] 是数组 [0,3,1,6,2,2…...

C语言:字符串函数strcpy

该函数用于字符串的拷贝。 使用方法如下&#xff1a; #include<stdio.h> #include<string.h>int main() {char str[10];char* str1 "abcd";//strcpy(str, str1);//把str1复制到str&#xff0c;但此函数不安全所以用strcpy_sstrcpy_s(str, 10, str1);/…...

Day16-指针2

数组指针与指针数组 变量指针&#xff1a;指向变量的地址。 数组指针&#xff1a;指向数组的地址。 指针变量&#xff1a;存放其他变量地址的变量。 指针数组&#xff1a;存放数组元素指针的变量。 数组指针 概念&#xff1a;数组指针是指向数组的指针。特点&#xff1a; 先…...

数据结构(5.5_3)——并查集的进一步优化

Find操作的优化(压缩路径) 压缩路径——Find操作&#xff0c;先找到根节点&#xff0c;再将查找路径上所有结点都挂到根结点下 代码&#xff1a; //Find "查"操作优化&#xff0c;先找到根节点&#xff0c;再进行"路径压缩" int Find(int S[], int x) {…...

(回溯) LeetCode 131. 分割回文串

原题链接 一. 题目描述 给你一个字符串 s&#xff0c;请你将 s 分割成一些子串&#xff0c;使每个子串都是 回文串。返回 s 所有可能的分割方案。 示例 1&#xff1a; 输入&#xff1a;s "aab" 输出&#xff1a;[["a","a","b"],[…...

【Linux】阻塞信号|信号原理|深入理解捕获信号|内核态|用户态|sigaction|可重入函数|volatile|SIGCHILD|万字详解

目录 ​编辑 一&#xff0c;常见的信号术语 二&#xff0c;信号在内核中的表示 信号标志位 Pending表 Block表 handler表 POSIX.1标准 三&#xff0c;sigset_t 信号集操作函数 sigemptyset sigfillset sigaddset sigdelset sigismember sigprocmask sig…...

基于Linux对 【进程地址空间】的详细讲解

研究背景&#xff1a; ● kernel 2.6.32 ● 32位平台 –❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀– 在学习操作系统中想必大家肯定都见过下面这…...

[python]使用Pandas处理多个Excel文件并汇总数据

在数据分析和处理过程中&#xff0c;经常需要处理多个Excel文件&#xff0c;并将其中的数据进行汇总和分析。本文介绍使用Python的Pandas库来读取多个Excel文件&#xff0c;并汇总不同类型的数据&#xff0c;例如员工工资、工件数量等。 代码示例 以下是一个完整的代码示例&a…...

提升体验:UI设计的可用性原则

在中国&#xff0c;每年都有数十万设计专业毕业生涌入市场&#xff0c;但只有少数能够进入顶尖企业。尽管如此&#xff0c;所有设计师都怀揣着成长和提升的愿望。在评价产品的用户体验时&#xff0c;我们可能会依赖直觉来决定设计方案&#xff0c;或者在寻找改善产品体验的切入…...

x264 编码器 SSIM 算法源码分析

SSIM SSIM(Structural Similarity Index)是一种用于衡量两幅图像之间视觉相似度的指标。它不仅考虑了图像的亮度、对比度和饱和度,还考虑了图像的结构信息。SSIM的值介于-1到1之间,值越接近1表示两幅图像越相似。 SSIM是基于以下三个方面来计算的: 亮度(Luminance):比…...

echarts使图表组件根据屏幕尺寸变更而重新渲染大小

效果图&#xff1a; 通过 window.addEventListener(resize, this.resizeChart); 实现 完整代码&#xff1a; <template><div class"dunBlock"><div class"char2" id"char2" ref"chart"></div></div…...

电脑图片损坏打不开怎么办?能修复吗?

照片和视频是记录和保存现实生活中的事件的最好方式。由于手机储存空间有限&#xff0c;一般我们会把有纪念意义的照片放到电脑上进行保存&#xff0c;但有时难免会遇到照片被损坏打不开的情况&#xff0c;一旦遇到这种情况&#xff0c;先不要急&#xff0c;也不要因为照片打不…...

vue-cli(二)

箭头函数 一般的函数&#xff1a; 这里window是用来调用函数的 function fun(){console.log(this) } window.fun(); 箭头函数&#xff1a; 1、如果只有一个参数&#xff0c;形参的小括号可以省略 2、如果只有一条语句&#xff0c;{}可以省略 完整的写法 let fun2 a>…...

今日头条的账号id在哪里看(网页版)

今日头条的账号id在哪里看&#xff08;网页版&#xff09; 1.https://mp.toutiao.com/profile_v4/index2.登录今日头条账号3.设置->头条号ID 1.https://mp.toutiao.com/profile_v4/index 2.登录今日头条账号 3.设置->头条号ID 打开下方链接&#xff1a; https://mp.to…...

单体应用提高性能和高并发处理-合理使用多核处理

合理使用多核处理能力是提升单体应用性能和处理高并发能力的重要手段。以下是关于如何合理利用多核处理器的详细讲解&#xff0c;包括多线程编程、线程池的使用、并行计算、以及如何避免常见的性能陷阱。 1. 多线程编程 多线程编程是利用多核处理器的直接方式。每个线程可以在…...

基于STM32/GD32的双CAN、一路485开发板

双CAN开发板 双CAN、一路485开发板的设计开发板配置器件选型CAN设计硬件设计软件设计 485设计硬件设计软件设计 其他设计LED硬件按键硬件 PCB板子和实物图开发板测试视频其他资料 双CAN、一路485开发板的设计 最近工作经常会出现一些小问题。就想设计一款带CAN的开发板用来测试…...

快排/堆排/归并/冒泡/

常见的内排序算法 插入排序 直接插入排序 原理&#xff1a;相当于扑克牌变成有序&#xff0c;先拿第一张&#xff0c;把他调节成有序&#xff0c;再拿第二张&#xff0c;与第一张相比找到第二张的位置&#xff0c;再继续拿第三张&#xff0c;以此类推。 void InsertSort(in…...

React基础教程(08):state体验

文章目录 7、state再体验7.1 异步更新状态7.2 同步更新状态方式17.3 同步更新状态方式27.4 betterScroll7.5 列表案例7、state再体验 7.1 异步更新状态 完整代码 import React from "react";export default class App extends React.Component{state = {count:1,}…...

Win10 创建新的桌面2,并实现桌面切换

1. Win10 创建新的桌面2 Win - Tab 2. Win10 桌面切换 Ctrl - Win - ←/→ 我们下期见&#xff0c;拜拜&#xff01;...

MySQL数据库介绍及基础操作

目录&#xff1a; 一.数据库介绍 二.数据库分类 三. 数据库的操作 四. 常用数据类型 五. 表的操作 一.数据库介绍 1.文件保存数据有以下几个缺点: 1.1文件的安全性问题 1.2文件不利于数据查询和管理 1.3文件不利于存储海量数据 1.4文件在程序中控制不方便 为了解决上述问题&…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...