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

子数组问题——动态规划

个人主页:敲上瘾-CSDN博客

动态规划

  • 基础dp:基础dp——动态规划-CSDN博客
  • 多状态dp:多状态dp——动态规划-CSDN博客

目录

一、解题技巧

二、最大子数组和

三、乘积最大子数组

四、最长湍流子数组

五、单词拆分


一、解题技巧

区分子数组(子串)与子序列:

  • 子数组(子串):在数列中的一段连续的元素组成的新数列,中间不可间断。
  • 子序列:在数列中从左往右依次挑选出元素组成的新数列,或者说在数列中随意删除一些元素后,剩下的元素组成的新数列。

用动态规划做子数组类的题时,对于状态表示我们可以直接设:

  • dp[i]为以i元素结尾的子数组的... ... 

        后面就根据具体的题目要求填写,可能是子数组的和或者子数组的积等等,无论如何都可以以i元素结尾的子数组为研究对象去思考问题,如果解决不了就尝试增加状态,但研究对象不要改变。如果还解决不了那么再考虑改变或增加研究对象。

二、最大子数组和

状态表示

如上技巧所述,我们直接设状态转移方程:

  • dp[i]表示:以i位置结尾的子数组的最大和。

接下来只需要去尝试是否能写出正确的状态转移方程,如果能那么状态表示就是对的。

状态转移方程:

以i位置结尾的子数组我们可以分为两种:

  1. nums[i]单独构成一个子数组
  2. nums[i]和以i-1结尾的最大和子数组组合成的子数组。

        那么这个以i-1结尾的最大子数组的值就是一个重复子问题,我们假设在前面已经计算过了,即dp[i-1],然后需要注意两种情况只能取一种。那么:

  • dp[i] = max(nums[i]+dp[i-1],nums[i])

初始化

初始化的目的主要有两个:

  • 保证填表的时候不越界。
  • 保证填表的正确性。

        因为这里有i-1,所以如果从0开始填表可能会越界,通常有两种解决方案:

        方法一:把dp[0]初始化(即dp[0]=nums[0]),然后从dp[1]位置开始填表(即从nums[1]位置开始记录)。

        方法二:开辟一个n+1的空间(n=nums.size()),让dp[0]=0(需要根据具体情况具体分析),然后从dp[1]位置开始填写,而dp[1]记录的是nums[0]的情况,也就是错开一位进行记录,所以需要注意映射关系。

        这题看似方法一更简洁,但对于其他题可能需要做更复杂的边界判断。所以在做动规题时更推荐使用方法二来解决边界问题。

填表顺序

        从左往右。

返回值

        dp表中的最大值。

代码示例:

class Solution 
{
public:int maxSubArray(vector<int>& nums){int n=nums.size(),ret=INT_MIN;vector<int> dp(n+1);for(int i=1;i<n+1;i++){dp[i]=max(nums[i-1],nums[i-1]+dp[i-1]);ret=max(ret,dp[i]);}    return ret;}
};

三、乘积最大子数组

状态表示

同样的我们假设状态表示为:

        dp[i]表示:以i位置结尾的子数组的最大乘积。

        那么状态转移方程dp[i]=max(dp[i-1]*nums[i],nums[i]),我们想一想这样对吗?比如dp[i-1]*nums[i],nums[i]乘以一个最大积的子数组就是最大吗?

        如果nums是一个负数不就变成最小乘积了吗,反之nums[i]小于0时乘以一个最小的数才能成为最大积。

        所以当nums[i]小于0时我们需要知道以i-1结尾的子数组的最小积。

所以状态表示为:

  • f[i]表示:以i位置结尾的子数组的最乘积。
  • g[i]表示:以i位置结尾的子数组的最乘积。

状态转移方程

  • nums[i]>=0:
    • f[i] = max(f[i-1]*nums[i],nums[i])
    • g[i] = min(g[i-1]*nums[i],nums[i])
  • nums[i] < 0:
    • f[i] = max(g[i-1]*nums[i],nums[i])
    • g[i] = min(f[i-1]*nums[i],nums[i])        

或:

  • f[i]=max(nums[i],max(nums[i]*f[i-1],nums[i]*g[i-1]));
  • g[i]=min(nums[i],min(nums[i]*f[i-1],nums[i]*g[i-1]));

初始化

        与上一题相同,为防止越界我们给两个dp表都多开辟一个空间,映射关系错开一位。

        然后把两个dp表都初始化为1,因为这里是乘法,如果使用默认的0值那么这个结果都是0。

注:dp[0]是我们为防止越界添加上的虚拟位置,它的值需要使得后面的填表正确。

填表顺序

        从左往右,f表和g表一起填。

返回值

        f表中的最大值。

代码示例:

class Solution {
public:int maxProduct(vector<int>& nums){int n=nums.size(), ret=INT_MIN;;vector<int> f(n+1,1),g(n+1,1);for(int i=1;i<=n;i++){f[i]=max(nums[i-1],max(nums[i-1]*f[i-1],nums[i-1]*g[i-1]));g[i]=min(nums[i-1],min(nums[i-1]*f[i-1],nums[i-1]*g[i-1]));ret=max(ret,f[i]);}return ret;}
};

四、最长湍流子数组

题目的核心就一句话:比较符号在子数组中的每个相邻元素对之间翻转。

然后找到满足这样的条件的最长子数组。

状态表示

假设状态表示为:

        dp[i]表示:以i结尾的最长湍流子数组。

我们把数据的大小波动抽象成一条折线,如下把示例1化为折线图:

结果取该段:

        也就是子数组要满足前一个元素是上升趋势那么下一个元素必须是下降,如果前一个元素是下降趋势那么下一个元素必须是上升。

我们在做状态转移方程中主要是考虑两种情况,

  1. nums[i]单独构成一个子数组
  2. nums[i]接到前一个元素结尾构成的子数组中。

第2种情况又需要分情况讨论,

  • nums[i] < nums[i-1]:只有前面的子数组最终状态是呈现上升趋势时nums[i]才能接上。
  • nums[i] > nums[i-1]:只有前面的子数组最终状态是呈现下降趋势时nums[i]才能接上。
  • nums[i]==nums[i-1]:不能接入前面子数组。

所以我们需要把状态转移细分为两种状态:

  • f[i]表示:以i结尾并且最后一个元素呈上升趋势的最长湍流子数组的长度
  • g[i]表示:以i结尾并且最后一个元素呈下降趋势的最长湍流子数组的长度

状态转移方程

  • nums[i] < nums[i-1]:
    • f[i]=1
    • g[i]=f[i-1]+1
  • nums[i] > nums[i-1]:
    • f[i]=g[i-1]+1
    • g[i]=1
  • nums[i]==nums[i-1]:
    • f[i]=1
    • g[i]=1

        因为任意一个子数组,最小的长度都是1,所以可以把两个dp表都初始化为1,那么状态转移方程可简化为:

  • nums[i] < nums[i-1]:g[i]+=f[i-1]
  • nums[i] > nums[i-1]:f[i]+=g[i-1]

初始化

        为防止越界我们给两个dp表都多开辟一个空间,映射关系错开一位。

        然后把两个dp表都初始化为1。

填表顺序

        从左往右,f表和g表同时填写。

返回值

        f表和g表中的最大那个元素

代码示例:

class Solution {
public:int maxTurbulenceSize(vector<int>& arr){int n=arr.size(),ret=1;vector<int> f(n,1),g(n,1);for(int i=1;i<n;i++){if(arr[i]<arr[i-1]) g[i]+=f[i-1];if(arr[i]>arr[i-1]) f[i]+=g[i-1];ret=max(ret,max(f[i],g[i]));}    return ret;}
};

五、单词拆分

状态表示

根据经验直接设状态表示:

  • dp[i]表示:从0到i位置结尾的字符串是否能被字典中的单词表示(bool类型)。

状态转移方程

        因为在填写i时以前的每个子串是否能由字典表示已经知道,储存在dp表中。那么我们只需要找到任意一个j(0<=j<i)使得dp[j]=true,并且子字符串[j+1,i]能用字典表示,那么dp[i]=true,否则dp[i]=false。

所以状态转移方程:

  • dp[i] = (dp[i-1]&&s[i,i]能用字典表示) || (dp[i-2]&&s[i-1,i]能用字典表示) || ... ... ||(dp[0]&&s[1,i]能用字典表示)

注:s[i-1,i]表示字符串中i-1到i这个子串。

初始化

        为了让第一个字符元素也讨论进来,我们创建n+1的dp表,并把dp[0]初始化为true。

填表顺序

        从左往右

返回值

        return dp[n]

代码示例:

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict){int n=s.size();unordered_set<string> st(wordDict.begin(),wordDict.end());vector<bool> dp(n+1);dp[0]=true;for(int i=1;i<=n;i++){for(int j=0;j<i;j++){if(dp[j]==false) continue;if(st.count(string(s.begin()+j,s.begin()+i))){dp[i]=true;break;}}}   return dp[n];}
};

好题推荐:

  • 53. 最大子数组和
  • 918. 环形子数组的最大和
  • 152. 乘积最大子数组
  • 1567. 乘积为正数的最长子数组长度
  • 413. 等差数列划分
  • 978. 最长湍流子数组
  • 139. 单词拆分
  • 467. 环绕字符串中唯一的子字符串

非常感谢您能耐心读完这篇文章。倘若您从中有所收获,还望多多支持呀!74c0781738354c71be3d62e05688fecc.png

相关文章:

子数组问题——动态规划

个人主页&#xff1a;敲上瘾-CSDN博客 动态规划 基础dp&#xff1a;基础dp——动态规划-CSDN博客多状态dp&#xff1a;多状态dp——动态规划-CSDN博客 目录 一、解题技巧 二、最大子数组和 三、乘积最大子数组 四、最长湍流子数组 五、单词拆分 一、解题技巧 区分子数组&…...

linux设置pem免密登录和密码登录

其实现在chatgpt 上面很多东西问题都可以找到比较好答案了&#xff0c;最近换了一个服务器&#xff0c;记录一下。 如果设置root用户&#xff0c;就直接切换到cd .ssh目录下生成ssh key即可&#xff0c;不需要创建用户创建用户的ssh文件夹了 比如说我要让danny这个用户可以用p…...

什么是Flask

Flask是Python中一个简单、灵活和易用的Web框架&#xff0c;适合初学者使用。它提供了丰富的功能和扩展性&#xff0c;可以帮助开发者快速构建功能完善的Web应用程序。 以下是Python Flask框架的一些特点和功能&#xff1a; Flask 是一个使用 Python 编写的轻量级 WSGI 微 Web…...

Spark(8)配置Hadoop集群环境-使用脚本命令实现集群文件同步

一.hadoop的运行模式 二.scp命令————基本使用 三.scp命令———拓展使用 四.rsync远程同步 五.xsync脚本集群之间的同步 一.hadoop的运行模式 hadoop一共有如下三种运行方式&#xff1a; 1. 本地运行。数据存储在linux本地&#xff0c;测试偶尔用一下。我们上一节课使用…...

【cocos creator】热更新

一、介绍 试了官方的热更新功能&#xff0c;总结一下 主要用于安卓包热更新 参考&#xff1a; Cocos Creator 2.2.2 热更新简易教程 基于cocos creator2.4.x的热更笔记 二、使用软件 1、cocos creator v2.4.10 2、creator热更新插件&#xff1a;热更新manifest生成工具&…...

黑金风格人像静物户外旅拍Lr调色教程,手机滤镜PS+Lightroom预设下载!

调色教程 针对人像、静物以及户外旅拍照片&#xff0c;运用 Lightroom 软件进行风格化调色工作。旨在通过软件中的多种工具&#xff0c;如基本参数调整、HSL&#xff08;色相、饱和度、明亮度&#xff09;调整、曲线工具等改变照片原本的色彩、明度、对比度等属性&#xff0c;将…...

部署vue+django项目(初版)

1.准备 vscode 插件Remote SSH&#xff0c;连接远程&#xff0c;打开远程中home文件夹。 镜像和容器的一些常用命令 docker images docker ps 查看所有正在运行的容器 docker ps -a docker rmi -f tk-django-app 删除镜像 docker rm xxx 删除容器 docker start xxxx …...

Redis7系列:设置开机自启

前面的文章讲了Redis和Redis Stack的安装&#xff0c;随着服务器的重启&#xff0c;导致Redis 客户端无法连接。原来的是Redis没有配置开机自启。此文记录一下如何配置开机自启。 1、修改配置文件 前面的Redis和Redis Stack的安装的文章中已经讲了redis.config的配置&#xf…...

HarmonyOS学习第18天:多媒体功能全解析

一、开篇引入 在当今数字化时代&#xff0c;多媒体已经深度融入我们的日常生活。无论是在工作中通过视频会议进行沟通协作&#xff0c;还是在学习时借助在线课程的音频讲解加深理解&#xff0c;亦或是在休闲时光用手机播放音乐放松身心、观看视频打发时间&#xff0c;多媒体功…...

在rocklinux里面批量部署安装rocklinx9

部署三台Rockylinux9服务器 实验要求 1. 自动安装ubuntu server20以上版本 2. 自动部署三台Rockylinux9服务器&#xff0c;最小化安装&#xff0c;安装基础包&#xff0c;并设定国内源&#xff0c;设静态IP 实验步骤 安装软件 # yum源必须有epel源 # dnf install -y epel-re…...

Manus:成为AI Agent领域的标杆

一、引言 官网&#xff1a;Manus 随着人工智能技术的飞速发展&#xff0c;AI Agent&#xff08;智能体&#xff09;作为人工智能领域的重要分支&#xff0c;正逐渐从概念走向现实&#xff0c;并在各行各业展现出巨大的应用潜力。在众多AI Agent产品中&#xff0c;Manus以其独…...

【Java开发指南 | 第三十四篇】IDEA没有Java Enterprise——解决方法

读者可订阅专栏&#xff1a;Java开发指南 |【CSDN秋说】 文章目录 1、新建Java项目2、单击项目名&#xff0c;并连续按两次shift键3、在搜索栏搜索"添加框架支持"4、勾选Web应用程序5、最终界面6、添加Tomcat 1、新建Java项目 2、单击项目名&#xff0c;并连续按两次…...

WinForm模态与非模态窗体

1、模态窗体 1&#xff09;定义&#xff1a; 模态窗体是指当窗体显示时&#xff0c;用户必须先关闭该窗体&#xff0c;才能继续与应用程序的其他部分进行交互。 2&#xff09;特点&#xff1a; 窗体以模态方式显示时&#xff0c;会阻塞主窗体的操作。用户必须处理完模态窗体上…...

静态时序分析:SDC约束命令set_ideal_network详解

相关阅读 静态时序分析https://blog.csdn.net/weixin_45791458/category_12567571.html?spm1001.2014.3001.5482 set_ideal_network命令可以将当前设计中的一组端口或引脚标记为理想网络源&#xff08;设置端口或引脚对象的ideal_network_source属性为true&#xff09;&#…...

【学习方法】技术开发者的提问智慧:如何高效获得解答?

技术开发者的提问智慧&#xff1a;如何高效获得解答&#xff1f; 在技术开发过程中&#xff0c;每个人都会遇到无法解决的问题。此时&#xff0c;我们通常会向团队、社区或论坛求助。然而&#xff0c;为什么有些人的问题能迅速得到解答&#xff0c;而有些人的问题却石沉大海&a…...

C++:入门详解(关于C与C++基本差别)

目录 一.C的第一个程序 二.命名空间&#xff08;namespace&#xff09; 1.命名空间的定义与使用&#xff1a; &#xff08;1&#xff09;命名空间里可以定义变量&#xff0c;函数&#xff0c;结构体等多种类型 &#xff08;2&#xff09;命名空间调用&#xff08;&#xf…...

服务器上的nginx因漏洞扫描需要升级

前言 最近客户联系说nginx存在安全漏洞 F5 Nginx 安全漏洞(CVE-2024-7347) F5Nginx是美国F5公司的一款轻量级Web服务器/反向代理服务器及电子邮件(IMAP/POP3)代理服务器&#xff0c;在BSD-like协议下发行。F5 Nginx存在安全漏洞&#xff0c;该漏洞源于可能允许攻击者使用特制的…...

1688商品列表商品详情API接口全面解析

1688作为中国领先的B2B电子商务平台&#xff0c;汇聚了海量的商品资源&#xff0c;为商家和采购商提供了丰富的交易机会。为了更方便地获取和利用这些商品信息&#xff0c;1688平台提供了商品列表API接口&#xff0c;允许第三方开发者通过编程方式获取平台上的商品列表数据。本…...

【爬虫】开篇词

一、网络爬虫概述 二、网络爬虫的应用场景 三、爬虫的痛点 四、需要掌握哪些技术&#xff1f; 在这个信息爆炸的时代&#xff0c;如何高效地获取和处理海量数据成为一项核心技能。无论是数据分析、商业情报、学术研究&#xff0c;还是人工智能训练&#xff0c;网络爬虫&…...

如何在SpringBoot中灵活使用异步事件?

在现代的应用开发中&#xff0c;事件驱动的架构越来越受到欢迎。当我们在使用SpringBoot时&#xff0c;了解如何实现异步事件变得尤为重要。通过事件机制&#xff0c;我们能够在系统中实现松耦合的组件&#xff0c;让不同模块之间能够有效沟通&#xff0c;而无需直接依赖。本文…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...