当前位置: 首页 > 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;而无需直接依赖。本文…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...