当前位置: 首页 > 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文件在程序中控制不方便 为了解决上述问题&…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...