刷代码随想录有感(122):动态规划——最长子序列

题干:

代码:

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

1.定义:dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

2.递推公式:

位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

所以:if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

注意这里不是要dp[i] 与 dp[j] + 1进行比较,而是我们要取dp[j] + 1的最大值,即:dp[i]为dp[j]+1的最大值,递推体现在由dp[j]+1推出dp[i]。

3.初始化:根据定义子序列一定不为空,所以都为1

4.遍历顺序:

dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来,那么遍历i一定是从前向后遍历。

j其实就是遍历0到i-1,那么是从前到后。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Windows 10,11 Server 2022 Install Docker-Desktop

docker 前言 Docker 是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的镜像中,然后发布到任何流行的 Linux或Windows 机器上,也可以实现虚拟化。容器是完全使用沙箱机制,相互之间不会有任何接口。 docker-compose Compose 是用于定义和运行…

14-10 AIGC 项目生命周期——第一阶段

生成式 AI 项目生命周期的整个过程类似于从范围、选择、调整和对齐/协调模型以及应用程序集成开始的顺序依赖过程。流程表明每个步骤都建立在前一步的基础上。有必要了解每个阶段对于项目的成功都至关重要。 下面的流程图重点介绍了生成式 AI 项目生命周期的第一阶段 1 — “范…

[数据集][目标检测]水面垃圾水面漂浮物检测数据集VOC+YOLO格式3749张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;3749 标注数量(xml文件个数)&#xff1a;3749 标注数量(txt文件个数)&#xff1a;3749 标注…

问题-小技巧-专业版Win11怎么启动电脑的休眠模式?

专业版Win11怎么启动电脑的休眠模式&#xff1f; powercfg -a powercfg -hibernate on 启用管理员面板依次输入上述命令就可以了。

Vue基础用法

Vue 定义&#xff1a; 是一套前端框架&#xff0c;免除原生JS中的DOM操作&#xff0c;简化书写&#xff0c;基于MVVM&#xff08;Model-View-ViewModel&#xff09;思想&#xff0c;实现数据的双向绑定&#xff0c;将编程的关注点放在数据上。 图来自黑马程序员网课 常用指令&…

性能测试中的场景设计和测试执行

假设一个内部系统要求响应时间在 3s 以内&#xff0c;支持最大用户数为4万。根据二八原则&#xff0c;80%用户在20%时间使用系统(4w80%)/(24h20%)≈1.9点击/秒。并发数TPS&#xff08;运行时间思考时间&#xff09;1.9&#xff08;30.50.330.50.30.53&#xff09;21。 注意&am…

大数据学习之Clickhouse

Clickhouse-23.2.1.2537 学习 一、Clickhouse概述 clickhouse 官网网址&#xff1a;https://clickhouse.com/ ClickHouse是一个用于联机分析(OLAP)的列式数据库管理系统(DBMS)。 OLTP(联机事务处理系统)例如mysql等关系型数据库&#xff0c;在对于存储小数据量的时候&#xff…

【论文复现|智能算法改进】基于自适应动态鲸鱼优化算法的路径规划研究

目录 1.算法原理2.改进点3.结果展示4.参考文献5.代码获取 1.算法原理 SCI二区|鲸鱼优化算法&#xff08;WOA&#xff09;原理及实现【附完整Matlab代码】 2.改进点 非线性收敛因子 WOA 主要通过控制系数向量 A 来决定鲸鱼是搜索猎物还是捕获猎物&#xff0c;即系数向量 A 可…

C语言部分复习笔记

1. 指针和数组 数组指针 和 指针数组 int* p1[10]; // 指针数组int (*p2)[10]; // 数组指针 因为 [] 的优先级比 * 高&#xff0c;p先和 [] 结合说明p是一个数组&#xff0c;p先和*结合说明p是一个指针 括号保证p先和*结合&#xff0c;说明p是一个指针变量&#xff0c;然后指…

适用于高海拔地区的工业路由器产品

1、西藏背景 西藏&#xff0c;这个位于中国西南部的神秘之地&#xff0c;以其雄伟壮观、神奇瑰丽的自然风光和深厚的文化底蕴&#xff0c;被无数人视为心中的圣地。这里属于高原性气候&#xff0c;具有气温低、气压低&#xff0c;降水少&#xff0c;生态环境十分恶劣。西藏被誉…

Coze搭建《测测你的本命宠物》

前言 本文讲解如何从零开始&#xff0c;使用扣子平台去搭建《测测你的本命宠物》 《测测你的本命宠物》&#xff1a;测测你的本命宠物 - 扣子 AI Bot (coze.cn) 欢迎大家去体验一下&#xff01;&#xff01;&#xff01; 正文 接下来我们开始讲解制作这个bot的流程吧&#…

【后端面试题】【中间件】【NoSQL】MongoDB的优点和分片机制

为什么要用MongoDB 两个关键&#xff1a;灵活性和横向扩展能力 MongoDB是灵活的文档模型&#xff0c;也就是说&#xff0c;如果预计我的数据可以被一个稳定的模型来描述&#xff0c;会倾向于使用MySQL等关系型数据库。而一旦我认为我的数据模型会经常变动&#xff0c;比如我很…

Jenkins接口自动化项目的工程创建

jenkins的下载安装 jenkins下载的官网地址 https://www.jenkins.io/download/ java环境变量的配置下载 jenkins是用java语言编写的所以要配置java环境 需要安装java的JDK 推荐安装JDK17(https://blog.csdn.net/wochunyang/article/details/138520209) JDK17的下载地址 ht…

CS144 Lab3 TCPSender复盘

一.基础概念 1.TCPSender在TCPSocket中的地位与作用 Lab0中实现了基于内存模拟的流控制-字节流&#xff08;ByteStream&#xff09;&#xff0c;底层使用std::deque实现&#xff0c;根据最大容量Capacity进行容量控制。个人理解它相当于应用层的输入输出缓存区&#xff0c;用户…

什么是电航空插头插座连接器有什么作用

航空插头概述 定义与功能 航空插头&#xff0c;又称航空连接器&#xff0c;是一种专门用于航空领域的电连接器&#xff0c;因其最初在航空领域得到广泛应用而得名。航空插头的主要功能是实现电源或信号的连接&#xff0c;尤其适用于芯数较多、结构复杂的线束连接&#xff0c;…

QT在VS环境中使用,控件显示中文乱码解决方法

首先来看乱码显示的效果如下&#xff1a; 上图左侧显示内容为中文&#xff0c;控件对应代码如下&#xff1a; QLabel* UserNameLabel new QLabel(QString("用户名&#xff1a;")); QLabel* NameLabel new QLabel(tr("姓名&#xff1a;"));下面我们对QL…

实现高效全自动印刷:直线模组的智能化应用

目前&#xff0c;直线模组被广泛应用于移载、定位、喷涂、夹取、搬运、点胶、涂胶、封胶、移载、装配、检测测量、切割、上下料、钻孔、焊接、等自动化行业中&#xff0c;尤其是自动印刷行业&#xff0c;跟直线模组也是息息相关的。那么&#xff0c;如何利用直线模组实现全自动…

C++进阶 | [4.3] 红黑树

摘要&#xff1a;什么是红黑树&#xff0c;模拟实现红黑树 红黑树 &#xff0c;是一种 二叉搜索树 &#xff0c;但 在每个结点上增加一个存储位表示结点的颜色&#xff0c;可以是 Red 或 Black 。 通过对 任何一条从根到叶子的路径上各个结点着色方式的限制&#xff0c;红黑树…

Web端登录页和注册页源码

前言&#xff1a;登录页面是前端开发中最常见的页面&#xff0c;下面是登录页面效果图和源代码&#xff0c;CV大法直接拿走。 1、登录页面 源代码&#xff1a; <!DOCTYPE html> <html><head><meta charset"utf-8"><title>登录</ti…

超详细的 C++中的封装继承和多态的知识总结<2.多态>

引言 小伙伴们我们都知道了&#xff0c;什么是封装和继承&#xff0c;在有了这个的基础上我们接着来看什么是多态。多态从字面上意思我们就可以知道&#xff0c;大概就是一个函数的不同形态&#xff0c;而且&#xff0c;前边我们在学习函数重载的时候我们已经简单的了解了如何用…