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

【动态规划】子序列系列

文章目录

  • 动态规划(子序列系列)
    • 1. 最长递增子序列
    • 2. 摆动序列
    • 3. 最长递增子序列的个数
    • 4. 最长数对链
    • 5. 最长定差子序列
    • 6. 最长的斐波那契子序列的长度
    • 7. 最长等差数列
    • 8. 等差数列划分 || - 子序列

动态规划(子序列系列)

1. 最长递增子序列

题目链接

  1. 状态表示

    dp[i]表示到 i 位置时,所有子序列当中最长的子序列的长度

  2. 状态转移方程

    image-20230731141850644

  3. 初始化

    表中的所有数据初始化为1

  4. 填表

    从左到右

  5. 返回值

    返回整个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. 摆动序列

题目链接

  1. 状态表示

    f[i]表示:以 i 位置为结尾的所有子序列当中,最后一个位置是上升的最长摆动序列的长度

    g[i]表示:以 i 位置为结尾的所有子序列当中,最后一个位置是下降的最长摆动序列的长度

  2. 状态转移方程

    gspg67wwyn-1690785946044.png

  3. 初始化

    表中的所有值初始化为1

  4. 填表

    从左到右

  5. 返回值

    返回两个表中的最大值

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;
}
  1. 状态表示

    len[i]表示以 i 位置为结尾所有子序列当中,最长递增子序列的长度

    count[i]表示以 i 位置为结尾所有子序列当中,最长递增子序列的个数

  2. 状态转移方程

    c46gcsfr8s-1690789206047.png

  3. 初始化

    所有值都初始化为1

  4. 填表

    从左到右

  5. 返回值

    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. 最长数对链

题目链接

分析:状态表示以某个位置为结尾的时候,后面的元素不能影响当前的填表,但是这个题目已经影响打了,所有需要将数组排序

  1. 状态表示

    dp[i]表示以 i 位置为结尾的所有数对链当中,最长的数对链的长度

  2. 状态转移方程

    wlx9ovlysc-1690791040047.png

  3. 初始化

    所有初始化为1

  4. 填表

    从做到右

  5. 返回值

    返回整个表的最大值

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. 最长定差子序列

题目链接

  1. 状态表示

    dp[i]表示到 i 位置时,所有的子序列当中最长的定差子序列的长度

  2. 状态转移方程

    iq9hs9xm3z-1690797357059.png

  3. 初始化

    将第一个元素对应的dp值初始化为1

  4. 填表

    从左到右

  5. 返回值

    返回整个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. 最长的斐波那契子序列的长度

题目链接

  1. 状态表示

    dp[i][j]表示以 i j 为结尾的所有子序列当中,最长的斐波那契数列的长度

  2. 状态转移方程

    uxobxtvs2s-1690810152050.png

    优化:将数组的元素和下标绑定,方便查找

  3. 初始化

  4. 填表

  5. 返回值

    返回值可能小于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. 最长等差数列

题目链接

  1. 状态表示

    dp[i][j] 表示 以 i j 为结尾的所有子序列当中最长的等差子序列的长度

  2. 状态转移方程

    n4g2m6wqhs-1690814489176.png

    优化:一边dp一边保存离它最近元素的下标,当 i 位置填完之后将它填入哈希表中即可。所以需要先固定第倒数第二个元素,接着固定倒数第一个元素

  3. 初始化

  4. 填表

  5. 返回值

    返回是整个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. 等差数列划分 || - 子序列

题目链接

  1. 状态表示

    dp[i][j]表示以 i j 为是等差数列的子序列的个数

  2. 状态表示

    n4g2m6wqhs-1690814489176.png

  3. 初始化

  4. 填表

  5. 返回值

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;}
};

相关文章:

【动态规划】子序列系列

文章目录 动态规划&#xff08;子序列系列&#xff09;1. 最长递增子序列2. 摆动序列3. 最长递增子序列的个数4. 最长数对链5. 最长定差子序列6. 最长的斐波那契子序列的长度7. 最长等差数列8. 等差数列划分 || - 子序列 动态规划&#xff08;子序列系列&#xff09; 1. 最长递…...

URL存储解锁数据管理的新思路,重新定义数据传输与共享(@vue/repl)

Thinking系列&#xff0c;旨在利用10分钟的时间传达一种可落地的编程思想。 近日&#xff0c;在了解 vue/repl 相关内容&#xff0c;其通过 URL 进行数据存储&#xff0c;感觉思路惊奇&#xff0c;打开了新方式。 首先&#xff0c;通过 URL 存储最大的便利是&#xff1a;无需服…...

matlab程序中文乱码

不同版本的matlab共存在GBK&#xff08;即&#xff0c;ANSI&#xff09;和UTF-8两种编码方式&#xff0c;因此可能会出现乱码问题。 第一步&#xff1a;在matlab的命令行窗口输入指令&#xff0c;查看当前编码方式 feature(locale) 第二步&#xff1a;用Notepad打开文件&…...

【计算机视觉|语音分离】期望在嘈杂环境中聆听:一个用于语音分离的不依赖于讲话者的“音频-视觉模型”

本系列博文为深度学习/计算机视觉论文笔记&#xff0c;转载请注明出处 标题&#xff1a;Looking to Listen at the Cocktail Party: A Speaker-Independent Audio-Visual Model for Speech Separation 链接&#xff1a;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 介绍 官网&#xff1a;https://curl.se/GitHub源码&#xff1a;https://github.com/curl/curl Curl…...

5、VMWARE安装、MobaXterm SSH连接 、Ubuntu xrdp安装使用

以下是在VMware中安装Ubuntu 22.04的详细步骤&#xff1a; 下载Ubuntu 22.04镜像文件&#xff1a; 前往Ubuntu官方网站或其他可信来源&#xff0c;下载Ubuntu 22.04的镜像文件&#xff08;.iso格式&#xff09;。 创建虚拟机&#xff1a; 打开VMware Workstation软件&#xf…...

Docker dockerfile 案例:centos 支持 vim

创建一个 centos 容器&#xff0c;容器内默认是不支持使用 vim 指令的&#xff0c;只能使用 vi 指令。&#xff08;附&#xff1a;Dockerfile 语法与指令&#xff09; 但想在创建 centos 容器后就支持 vim 指令&#xff0c;需要自定义 centos&#xff0c;编写 dockerfile&…...

Git忽略已经提交过一次的文件 Git忽略文件

1、从未提交过的文件可以用.gitignore 也就是添加之后从来没有提交&#xff08;commit&#xff09;过的文件&#xff0c;可以使用.gitignore忽略该文件 该文件只能作用于未跟踪的文件&#xff08;Untracked Files&#xff09;&#xff0c;也就是那些从来没有被 git 记录过…...

Scala项目找不到或无法加载主类

目录 1&#xff0c;出错背景2&#xff0c;分析与解决 1&#xff0c;出错背景 Scala项目无法创建scale和Java文件。项目没有报错&#xff0c;但执行时项目总是找不到项目下的类&#xff0c;报错信息如下所示&#xff1a; 错误: 找不到或无法加载主类 com.my.memTestCheck但该类…...

八大排序算法--选择排序(动图理解)

选择排序 算法思路 每一次从待排序的数据元素中选出最小&#xff08;或最大&#xff09;的一个元素&#xff0c;存放在序列的起始位置&#xff0c;直到全部待排序的数据元素排完 。 选择排序的步骤&#xff1a; 1>首先在未排序序列中找到最小&#xff08;大&#xff09;元素…...

6.s081(Fall 2022)Lab2: system calls

文章目录 前言其他篇章参考链接0. 前置准备1. System call tracing (moderate) 前言 好像没啥前言 其他篇章 环境搭建 Lab1:Utilities 参考链接 官网链接 xv6手册链接&#xff0c;这个挺重要的&#xff0c;建议做lab之前最好读一读。 xv6手册中文版&#xff0c;这是几位先…...

SAMBA 文件分享相关 笔记

目标说明 在Linux 安装Samba&#xff0c;然后在Windows端映射为网络硬盘 流程 Linux 端命令 apt install samba -y 默认情况下软件会询问是否迁移系统网络设置以搭建协议&#xff0c;选择迁移即可修改配置文件 vim /etc/samba/smb.conf Samba 的配置文件中会带一个名为 prin…...

Mr. Cappuccino的第53杯咖啡——Mybatis源码分析

Mybatis源码分析 Mybatis源码分析入口1. 读取配置文件总结 2. 解析配置文件核心代码&#xff08;一&#xff09;核心代码&#xff08;二&#xff09;分析parse()方法分析build()方法 总结 3. 获取SqlSession总结 4. 获取mapper代理对象总结 5. 使用mapper代理对象执行Sql语句二…...

修改文件格式(查看文件拓展名)

很多时候我们直接把txt文件重命名为xxx.c或者别的文件格式&#xff0c;文件类型依然会是txt&#xff0c;文件名并不会变成我们想要的xxx.c&#xff0c;而是xxx.c.txt&#xff0c;也就是下面这个样子 给大家介绍2种方法去解决这个问题 目录 1.另存为新格式 2.显示文件拓展名 1…...

利用鸿鹄可观测性监控Istio Ingress网关

一、需求描述 在上一篇《利用Vector和鸿鹄搭建微服务应用的可观测性平台》中&#xff0c;阐述了微服务的基本概念、优点及如何利用鸿鹄来处理分布式应用的日志。本文将进一步讨论微服务架构面临的问题、服务网格及鸿鹄处理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黄金最新行情走势分析及多空交易策略

近期有哪些消息面影响黄金走势&#xff1f;黄金多空该如何研判&#xff1f; ​黄金消息面解析&#xff1a;上周有重磅数据美联储加息的消息&#xff0c;黄金受其影响波动比较频繁&#xff0c;总体空间40美金。但这个过程跌宕起伏。收线来看黄金在连续上涨三周后迎来一根小阴十…...

Spring框架——AOP注解方式

目录 Spring框架的AOP技术&#xff08;注解方式&#xff09; 通知类型 Spring框架的AOP技术&#xff08;注解方式&#xff09; 1. 步骤一&#xff1a;创建JavaWEB项目&#xff0c;引入具体的开发的jar包* 先引入Spring框架开发的基本开发包com.springsource.org.apache.commo…...

Java 日志(Logging)如何创建和捕获日志消息和文件

Java允许我们通过日志记录过程来创建和捕获日志消息和文件。 在Java中&#xff0c;日志记录需要框架和API。Java在java.util.logging程序包中具有内置的日志记录框架。 Java 日志组件 下图显示了Java Logging API&#xff08;java.util.logging&#xff09;的核心组件和指定…...

避开SAP记账第一个坑:F-02凭证录入的5个细节与FS10N对账技巧

SAP财务实操避坑指南&#xff1a;F-02凭证录入的5个关键细节与FS10N高效对账技巧 刚接触SAP FI模块的中级用户&#xff0c;往往在完成基础培训后信心满满地开始独立操作&#xff0c;却在F-02凭证录入时频频踩坑。这些看似简单的字段选择背后&#xff0c;隐藏着财务逻辑与系统设…...

React Overdrive核心组件深度解析:从API到实战

React Overdrive核心组件深度解析&#xff1a;从API到实战 【免费下载链接】react-overdrive Super easy magic-move transitions for React apps 项目地址: https://gitcode.com/gh_mirrors/re/react-overdrive React Overdrive是一款专为React应用设计的终极魔法移动过…...

DeepSeek-OCR-2应用实战:快速提取发票信息,财务效率翻倍

DeepSeek-OCR-2应用实战&#xff1a;快速提取发票信息&#xff0c;财务效率翻倍 1. 财务人的痛点&#xff1a;发票处理的效率黑洞 每个月末&#xff0c;财务部门总要面对这样的场景&#xff1a; 堆积如山的纸质发票需要手工录入电子发票PDF需要逐个打开复制粘贴关键信息&…...

PCL-CE深度指南:从基础配置到高级定制的全流程解析

PCL-CE深度指南&#xff1a;从基础配置到高级定制的全流程解析 PCL-CE作为社区驱动的Minecraft启动器增强版&#xff0c;集成了多版本管理、智能模组兼容和网络优化等核心功能&#xff0c;为玩家提供高效便捷的游戏环境配置工具。无论是新手玩家还是资深爱好者&#xff0c;都能…...

CS231n实战解析:从HOG/HSV特征到图像分类性能提升

1. 图像特征工程入门&#xff1a;为什么HOG和HSV如此重要 第一次接触CS231n作业时&#xff0c;我对HOG和HSV这两个特征提取方法感到既陌生又好奇。直到在CIFAR-10数据集上做了对比实验才发现&#xff0c;使用原始像素训练的模型准确率只有0.51&#xff0c;而加入特征工程后直接…...

从收音机到WiFi:LC并联谐振电路在实际通信系统里是怎么用的?

从矿石收音机到5G基站&#xff1a;LC并联谐振电路的百年进化史 当你拧动老式收音机的调谐旋钮时&#xff0c;金属指针在刻度盘上滑过不同电台的频率标记&#xff0c;耳机里传来忽大忽小的静电噪声&#xff0c;直到某个瞬间——声音突然清晰起来。这个看似简单的动作背后&#x…...

电子电路实战:PWM转DAC的滤波参数优化策略

1. PWM转DAC的基础原理 PWM&#xff08;脉冲宽度调制&#xff09;转DAC&#xff08;数模转换&#xff09;是嵌入式系统中常见的低成本解决方案。简单来说&#xff0c;就是通过调节数字信号的占空比来模拟不同的电压值。比如一个3.3V的PWM信号&#xff0c;50%占空比就相当于1.65…...

Fastboot Enhance:高效Android刷机工具与Payload管理平台

Fastboot Enhance&#xff1a;高效Android刷机工具与Payload管理平台 【免费下载链接】FastbootEnhance A user-friendly Fastboot ToolBox & Payload Dumper for Windows 项目地址: https://gitcode.com/gh_mirrors/fa/FastbootEnhance 价值定位&#xff1a;重新定…...

高速ADC采样时钟不准?手把手教你理解时钟占空比校正(DCC)电路的核心原理

高速ADC采样时钟不准&#xff1f;手把手教你理解时钟占空比校正&#xff08;DCC&#xff09;电路的核心原理 当你在调试一块高速ADC板卡时&#xff0c;发现ENOB&#xff08;有效位数&#xff09;始终比规格书低2-3位&#xff0c;频谱分析显示谐波失真异常。这种困扰可能来自一…...

快速搭建视觉定位服务:Chord(Qwen2.5-VL)一键部署与使用

快速搭建视觉定位服务&#xff1a;Chord&#xff08;Qwen2.5-VL&#xff09;一键部署与使用 1. 项目概述 Chord是基于Qwen2.5-VL多模态大模型的视觉定位服务&#xff0c;能够通过自然语言描述在图像中精确定位目标对象。想象一下&#xff0c;你只需要说"找到图里的白色花…...