【动态规划】子序列系列
文章目录
- 动态规划(子序列系列)
- 1. 最长递增子序列
- 2. 摆动序列
- 3. 最长递增子序列的个数
- 4. 最长数对链
- 5. 最长定差子序列
- 6. 最长的斐波那契子序列的长度
- 7. 最长等差数列
- 8. 等差数列划分 || - 子序列
动态规划(子序列系列)
1. 最长递增子序列
题目链接
-
状态表示
dp[i]表示到 i 位置时,所有子序列当中最长的子序列的长度 -
状态转移方程

-
初始化
表中的所有数据初始化为1
-
填表
从左到右
-
返回值
返回整个dp表里面最大的值
AC代码:
class Solution
{
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> dp(n, 1);int ret = 1;for (int i = 1; i < n; i++){for (int j = 0; j < i; j++){if (nums[i] > nums[j]){dp[i] = max(dp[i], dp[j] + 1);}}ret = max(ret, dp[i]);}return ret;}
};
2. 摆动序列
题目链接
-
状态表示
f[i]表示:以 i 位置为结尾的所有子序列当中,最后一个位置是上升的最长摆动序列的长度g[i]表示:以 i 位置为结尾的所有子序列当中,最后一个位置是下降的最长摆动序列的长度 -
状态转移方程

-
初始化
表中的所有值初始化为1
-
填表
从左到右
-
返回值
返回两个表中的最大值
AC代码:
class Solution
{
public:int wiggleMaxLength(vector<int>& nums) {int n = nums.size();vector<int> f(n, 1), g(n, 1);int ret = 1;for (int i = 1; i < n; i++){for (int j = 0; j < i; j++){if (nums[i] > nums[j]) f[i] = max(f[i], g[j] + 1);else if (nums[i] < nums[j]) g[i] = max(g[i], f[j] + 1);}ret = max(ret, max(f[i], g[i]));}return ret;}
};
3. 最长递增子序列的个数
题目链接
这里需要用到一种思想:
如何一次遍历数组,就可以找到最大数出现的次数
代码实现:
#include <iostream>using namespace std;int main()
{int arr[] = {2, 3, 1, 234, 43, 342, 234, 5, 34, 43, 8, 342};int n = sizeof(arr)/sizeof(arr[0]);int maxval = 0;int count = 0;for (int i = 0; i < n; i++){if (arr[i] > maxval) maxval = arr[i], count = 1;else if (arr[i] == maxval) count++;}cout << maxval << endl;cout << count << endl;return 0;
}
-
状态表示
len[i]表示以 i 位置为结尾所有子序列当中,最长递增子序列的长度count[i]表示以 i 位置为结尾所有子序列当中,最长递增子序列的个数 -
状态转移方程

-
初始化
所有值都初始化为1
-
填表
从左到右
-
返回值
count表最后一个
AC代码:
class Solution
{
public:int findNumberOfLIS(vector<int>& nums) {int n = nums.size();vector<int> len(n, 1), count(n, 1);int retval = 1, retcount = 1;for (int i = 1; i < n; i++){for (int j = 0; j < i; j++){if (nums[i] > nums[j]){if (len[j] + 1 > len[i]) len[i] = len[j] + 1, count[i] = count[j];else if (len[j] + 1 == len[i]) count[i] += count[j];}}if (retval == len[i]) retcount += count[i];else if (retval < len[i]) retval = len[i], retcount = count[i];}return retcount;}
};
4. 最长数对链
题目链接
分析:状态表示以某个位置为结尾的时候,后面的元素不能影响当前的填表,但是这个题目已经影响打了,所有需要将数组排序
-
状态表示
dp[i]表示以 i 位置为结尾的所有数对链当中,最长的数对链的长度 -
状态转移方程

-
初始化
所有初始化为1
-
填表
从做到右
-
返回值
返回整个表的最大值
AC代码:
class Solution
{
public:int findLongestChain(vector<vector<int>>& pairs) {sort(pairs.begin(), pairs.end());int n = pairs.size();vector<int> dp(n, 1);int ret = 1;for (int i = 1; i < n; i++){for (int j = 0; j < i; j++){if (pairs[i][0] > pairs[j][1]) {dp[i] = max(dp[i], dp[j] + 1);}}ret = max(ret, dp[i]);}return ret;}
};
5. 最长定差子序列
题目链接
-
状态表示
dp[i]表示到 i 位置时,所有的子序列当中最长的定差子序列的长度 -
状态转移方程

-
初始化
将第一个元素对应的dp值初始化为1
-
填表
从左到右
-
返回值
返回整个dp表里的最大值
AC代码:
class Solution
{
public:int longestSubsequence(vector<int>& arr, int difference) {unordered_map<int, int> hash;hash[arr[0]] = 1;int ret = 1;for (int i = 1; i < arr.size(); i++){hash[arr[i]] = hash[arr[i] - difference] + 1;ret = max(ret, hash[arr[i]]);}return ret;}
};
6. 最长的斐波那契子序列的长度
题目链接
-
状态表示
dp[i][j]表示以 i j 为结尾的所有子序列当中,最长的斐波那契数列的长度 -
状态转移方程

优化:将数组的元素和下标绑定,方便查找
-
初始化
-
填表
-
返回值
返回值可能小于3, 这是应该返回0
AC代码:
class Solution
{
public:int lenLongestFibSubseq(vector<int>& arr) {int n = arr.size();unordered_map<int, int> hash;for (int i = 0; i < n; i++) hash[arr[i]] = i;vector<vector<int>> dp(n, vector<int>(n, 2));int ret = 2;for (int j = 2; j < n; j++) // 固定最后一个位置{for (int i = 1; i < j; i++){int a = arr[j] - arr[i];if (a < arr[i] && hash.count(a)){dp[i][j] = dp[hash[a]][i] + 1;}ret = max(ret, dp[i][j]);}}return ret < 3 ? 0 : ret;}
};
7. 最长等差数列
题目链接
-
状态表示
dp[i][j] 表示 以 i j 为结尾的所有子序列当中最长的等差子序列的长度 -
状态转移方程

优化:一边dp一边保存离它最近元素的下标,当 i 位置填完之后将它填入哈希表中即可。所以需要先固定第倒数第二个元素,接着固定倒数第一个元素
-
初始化
-
填表
-
返回值
返回是整个dp表里的最大值
AC代码:
class Solution
{
public:int longestArithSeqLength(vector<int>& nums) {unordered_map<int, int> hash;int n = nums.size();hash[nums[0]] = 0;vector<vector<int>> dp(n, vector<int>(n, 2));int ret = 2;for (int i = 1; i < n; i++){for (int j = i + 1; j < n; j++){int a = 2 * nums[i] - nums[j];if (hash.count(a)){dp[i][j] = dp[hash[a]][i] + 1;}ret = max(ret, dp[i][j]);}hash[nums[i]] = i;}return ret;}
};
8. 等差数列划分 || - 子序列
题目链接
-
状态表示
dp[i][j]表示以 i j 为是等差数列的子序列的个数 -
状态表示

-
初始化
-
填表
-
返回值
AC代码:
class Solution
{
public:int numberOfArithmeticSlices(vector<int>& nums) {int n = nums.size();unordered_map<long long, vector<int>> hash;for (int i = 0; i < n; i++) hash[nums[i]].push_back(i);vector<vector<int>> dp(n, vector<int>(n));int sum = 0;for (int j = 2; j < n; j++) // 固定倒数第一个{for (int i = 1; i < j; i++){long long a = (long long)nums[i] * 2 - nums[j];if (hash.count(a)){for (auto k : hash[a]){if (k < i) dp[i][j] += dp[k][i] + 1;else break;}}sum += dp[i][j];}}return sum;}
};
相关文章:
【动态规划】子序列系列
文章目录 动态规划(子序列系列)1. 最长递增子序列2. 摆动序列3. 最长递增子序列的个数4. 最长数对链5. 最长定差子序列6. 最长的斐波那契子序列的长度7. 最长等差数列8. 等差数列划分 || - 子序列 动态规划(子序列系列) 1. 最长递…...
URL存储解锁数据管理的新思路,重新定义数据传输与共享(@vue/repl)
Thinking系列,旨在利用10分钟的时间传达一种可落地的编程思想。 近日,在了解 vue/repl 相关内容,其通过 URL 进行数据存储,感觉思路惊奇,打开了新方式。 首先,通过 URL 存储最大的便利是:无需服…...
matlab程序中文乱码
不同版本的matlab共存在GBK(即,ANSI)和UTF-8两种编码方式,因此可能会出现乱码问题。 第一步:在matlab的命令行窗口输入指令,查看当前编码方式 feature(locale) 第二步:用Notepad打开文件&…...
【计算机视觉|语音分离】期望在嘈杂环境中聆听:一个用于语音分离的不依赖于讲话者的“音频-视觉模型”
本系列博文为深度学习/计算机视觉论文笔记,转载请注明出处 标题:Looking to Listen at the Cocktail Party: A Speaker-Independent Audio-Visual Model for Speech Separation 链接:Looking to listen at the cocktail party: a speaker-in…...
curl 介绍和使用
文章目录 一、介绍1.1 curl 介绍1.2 curl 参数介绍1.3 类似Curl的工具和库 二、使用2.1 curl 下载2.2 curl 示例用法2.3 curl命令使用digest方式验证用户 一、介绍 1.1 curl 介绍 官网:https://curl.se/GitHub源码:https://github.com/curl/curl Curl…...
5、VMWARE安装、MobaXterm SSH连接 、Ubuntu xrdp安装使用
以下是在VMware中安装Ubuntu 22.04的详细步骤: 下载Ubuntu 22.04镜像文件: 前往Ubuntu官方网站或其他可信来源,下载Ubuntu 22.04的镜像文件(.iso格式)。 创建虚拟机: 打开VMware Workstation软件…...
Docker dockerfile 案例:centos 支持 vim
创建一个 centos 容器,容器内默认是不支持使用 vim 指令的,只能使用 vi 指令。(附:Dockerfile 语法与指令) 但想在创建 centos 容器后就支持 vim 指令,需要自定义 centos,编写 dockerfile&…...
Git忽略已经提交过一次的文件 Git忽略文件
1、从未提交过的文件可以用.gitignore 也就是添加之后从来没有提交(commit)过的文件,可以使用.gitignore忽略该文件 该文件只能作用于未跟踪的文件(Untracked Files),也就是那些从来没有被 git 记录过…...
Scala项目找不到或无法加载主类
目录 1,出错背景2,分析与解决 1,出错背景 Scala项目无法创建scale和Java文件。项目没有报错,但执行时项目总是找不到项目下的类,报错信息如下所示: 错误: 找不到或无法加载主类 com.my.memTestCheck但该类…...
八大排序算法--选择排序(动图理解)
选择排序 算法思路 每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。 选择排序的步骤: 1>首先在未排序序列中找到最小(大)元素…...
6.s081(Fall 2022)Lab2: system calls
文章目录 前言其他篇章参考链接0. 前置准备1. System call tracing (moderate) 前言 好像没啥前言 其他篇章 环境搭建 Lab1:Utilities 参考链接 官网链接 xv6手册链接,这个挺重要的,建议做lab之前最好读一读。 xv6手册中文版,这是几位先…...
SAMBA 文件分享相关 笔记
目标说明 在Linux 安装Samba,然后在Windows端映射为网络硬盘 流程 Linux 端命令 apt install samba -y 默认情况下软件会询问是否迁移系统网络设置以搭建协议,选择迁移即可修改配置文件 vim /etc/samba/smb.conf Samba 的配置文件中会带一个名为 prin…...
Mr. Cappuccino的第53杯咖啡——Mybatis源码分析
Mybatis源码分析 Mybatis源码分析入口1. 读取配置文件总结 2. 解析配置文件核心代码(一)核心代码(二)分析parse()方法分析build()方法 总结 3. 获取SqlSession总结 4. 获取mapper代理对象总结 5. 使用mapper代理对象执行Sql语句二…...
修改文件格式(查看文件拓展名)
很多时候我们直接把txt文件重命名为xxx.c或者别的文件格式,文件类型依然会是txt,文件名并不会变成我们想要的xxx.c,而是xxx.c.txt,也就是下面这个样子 给大家介绍2种方法去解决这个问题 目录 1.另存为新格式 2.显示文件拓展名 1…...
利用鸿鹄可观测性监控Istio Ingress网关
一、需求描述 在上一篇《利用Vector和鸿鹄搭建微服务应用的可观测性平台》中,阐述了微服务的基本概念、优点及如何利用鸿鹄来处理分布式应用的日志。本文将进一步讨论微服务架构面临的问题、服务网格及鸿鹄处理Istio Gateway的独特优势。 1.1 微服务架构面临的挑战 …...
vscode 前端开发插件 2023
自己记录 安装vscode后必装插件 chinesegit 必装没啥可说 随时更新 1.CSS Navigation CTRL点击类名可跳转到对应样式位置。 如果是scss less的话。css peak插件无法生效 2.GitLens — Git supercharged 可以看到每一行的git提交记录。 3.Auto Rename Tag 可以同步更新…...
使用docker部署Wordpress
文章目录 1.创建网络2.创建volume存储3.拉取镜像4.创建mysql容器mysql修改密码 5.创建wordpress容器6.访问localhost:80就可以直接使用啦 1.创建网络 docker network create --subnet172.18.0.0/24 pro-net2.创建volume存储 # mysql 存储 docker volume create volume_mysql…...
7.31黄金最新行情走势分析及多空交易策略
近期有哪些消息面影响黄金走势?黄金多空该如何研判? 黄金消息面解析:上周有重磅数据美联储加息的消息,黄金受其影响波动比较频繁,总体空间40美金。但这个过程跌宕起伏。收线来看黄金在连续上涨三周后迎来一根小阴十…...
Spring框架——AOP注解方式
目录 Spring框架的AOP技术(注解方式) 通知类型 Spring框架的AOP技术(注解方式) 1. 步骤一:创建JavaWEB项目,引入具体的开发的jar包* 先引入Spring框架开发的基本开发包com.springsource.org.apache.commo…...
Java 日志(Logging)如何创建和捕获日志消息和文件
Java允许我们通过日志记录过程来创建和捕获日志消息和文件。 在Java中,日志记录需要框架和API。Java在java.util.logging程序包中具有内置的日志记录框架。 Java 日志组件 下图显示了Java Logging API(java.util.logging)的核心组件和指定…...
解锁Linux平台微信小程序开发:终极完整环境搭建指南
解锁Linux平台微信小程序开发:终极完整环境搭建指南 【免费下载链接】wechat-web-devtools-linux 适用于微信小程序的微信开发者工具 Linux移植版 项目地址: https://gitcode.com/gh_mirrors/we/wechat-web-devtools-linux 你是否曾为在Linux系统上无法使用微…...
禅道16.4开源版二次开发实战:手把手教你给测试用例新增“测试方式”字段(附完整代码)
禅道16.4开源版二次开发实战:从零构建测试方式字段全流程指南 当测试团队同时管理手工与自动化用例时,原生禅道系统缺少测试类型标识字段的问题会直接导致统计混乱。上周我接手的一个金融项目就遇到这种情况——自动化测试报告总是混入手工用例数据。经过…...
从DCM到NII:医学影像数据处理中,为什么我劝你放弃保存回DCM格式?
从DCM到NII:医学影像数据处理中格式选择的深度实践指南 医学影像数据处理的流程中,文件格式的选择往往被忽视,却直接影响着后续分析的效率与兼容性。许多研究者习惯性地将处理后的数据保存回DCM格式,殊不知这可能在后续流程中埋下…...
突破QQ音乐格式限制:QMCFLAC2MP3的音乐自由解决方案
突破QQ音乐格式限制:QMCFLAC2MP3的音乐自由解决方案 【免费下载链接】qmcflac2mp3 直接将qmcflac文件转换成mp3文件,突破QQ音乐的格式限制 项目地址: https://gitcode.com/gh_mirrors/qm/qmcflac2mp3 QMCFLAC2MP3是一款专为破解QQ音乐格式限制设计…...
DOMPurify实战:如何在Node.js后端安全处理用户HTML输入(附最新jsdom配置)
DOMPurify实战:如何在Node.js后端安全处理用户HTML输入(附最新jsdom配置) 当用户提交的HTML内容直接进入数据库时,就像给黑客开了扇后门。去年某知名博客平台因未过滤富文本评论,导致攻击者通过精心构造的<img srcx…...
WarcraftHelper解决方案:魔兽争霸3跨系统优化指南
WarcraftHelper解决方案:魔兽争霸3跨系统优化指南 【免费下载链接】WarcraftHelper Warcraft III Helper , support 1.20e, 1.24e, 1.26a, 1.27a, 1.27b 项目地址: https://gitcode.com/gh_mirrors/wa/WarcraftHelper 魔兽争霸3作为经典的即时战略游戏&#…...
Phi-4-mini-reasoning推理服务监控:通过webshell日志诊断部署状态方法
Phi-4-mini-reasoning推理服务监控:通过webshell日志诊断部署状态方法 1. 模型简介 Phi-4-mini-reasoning 是一个基于合成数据构建的轻量级开源模型,专注于高质量、密集推理的数据处理。作为Phi-4模型家族的一员,它经过专门微调以提升数学推…...
告别迷茫!Quartus II 13.1 从新建工程到烧录FPGA的保姆级避坑指南
Quartus II 13.1实战指南:从零开始玩转FPGA开发 第一次打开Quartus II 13.1时,那个灰蒙蒙的界面和密密麻麻的菜单栏确实容易让人望而生畏。作为Altera(现已被Intel收购)旗下经典的FPGA开发工具,它在高校实验室和企业研…...
快速验证模型服务:AutoGen Studio中连接vLLM部署的Qwen3-4B
快速验证模型服务:AutoGen Studio中连接vLLM部署的Qwen3-4B 1. 环境准备与快速部署 1.1 镜像启动与基础检查 首先确保已成功启动AutoGen Studio镜像,该镜像已预置vLLM部署的Qwen3-4B-Instruct-2507模型服务。验证模型服务是否正常运行: c…...
收藏!小白也能入局:2026年最火高薪AI Agent开发指南(年薪80万+)
文章介绍了Agentic AI(AI Agent)的兴起及其对职场的巨大影响。通过一个真实案例展现了个人通过学习AI从月薪8K到年薪80万的转变。文章指出,到2026年,40%的岗位将与AI Agent协作,年薪10万美元起步的职位需求激增。文章详…...
