对于子数组问题的动态规划

前言

先讲讲我对于这个问题的理解吧

当谈到解决子数组问题时,动态规划(DP)是一个强大的工具,它在处理各种算法挑战时发挥着重要作用。动态规划是一种思想,它通过将问题分解成更小的子问题并以一种递归的方式解决它们,然后利用这些解决方案来构建原始问题的解。在动态规划中,我们经常会遇到两种状态:一种是单独成一段,另一种是以 i 结尾的子数组。

通过枚举和动态规划,我们可以有效地解决子数组问题。枚举法需要考虑所有可能的子数组组合,然后比较它们以找到最优解。这种方法通常需要较多的时间和空间,因为它需要枚举所有可能性。而动态规划则更加智能化,它通过保存历史记录来避免不必要的重复计算。这样,下次遍历时,我们可以利用之前的计算结果,从而大大提高了效率。

动态规划的一个常见技巧是前缀和,它可以帮助我们快速求出数组中任意子数组的和。前缀和的核心思想是将原始数组中每个位置的值累加起来,形成一个新的数组,然后利用这个新数组来快速计算子数组的和。这种方法在处理求子数组和的问题时非常实用,因为它将复杂度降低到了单一状态的动态规划。

另外,预处理也是动态规划中常用的技巧之一。通过将经常使用的数据存储起来,我们可以在需要时快速获取,从而减少计算时间。预处理的思想是在问题出现之前就对数据进行处理,以便在需要时能够迅速获取所需的信息。

综上所述,动态规划是一种强大的解决子数组问题的方法,通过合理利用枚举、动态规划、前缀和和预处理等技巧,我们可以高效地解决各种复杂的算法挑战,为问题提供简单明了的解决方案。

这是我记得笔记 

 

我准备了五道例题都是这些解决方案

1.求最大子数组的和

. - 力扣(LeetCode)

思路分析:这一题主要是使用动态规划,也可以使用前缀和,动态规划也是求子数组的普遍思路,有两种状态,1自己组成子数组 和 前面的组成子数组,所以状态转移方程也就是Max(nums[i],dp[i - 1] + nums[i])

 代码实现

  public int maxSubArray(int[] nums) {int n = nums.length;int[] dp = new int[n + 1];//以i位置为结尾的最大子数组和 (多状态 前面i - 1的子数组要  和 不要)// 初始化 (因为存在负数)dp[0] = -0x3f3f3f3f;//前面子数组都是以i - 1位置为结尾 或者 i位置自己构成一个数组for (int i = 1; i <= nums.length; i++) {dp[i] = Math.max(nums[i - 1], dp[i - 1] + nums[i - 1]);}int max = -0x3f3f3f3f;for (int i = 0; i < dp.length; i++) {max = Math.max(dp[i], max);}return max;}

2.求最大环形子数组

. - 力扣(LeetCode)

思路分析:

中间的是连续的所以求内部最小子数组和就好了, 或者中间成最大子数组和
//f[]表示以i位置为结尾的所有子数组中的最大值  //g[]表示以i位置为结尾的所有子数组中的最小值
//g[]就是为了处理边界。他通过计算中间部分的最小值来结算环的最大值

public int maxSubarraySumCircular(int[] nums) {int sum = 0;//用来处理最小值int n = nums.length;//1.状态表示int[] f = new int[n + 1],g = new int[n + 1];//2.状态转移方程    自己组成子数组  和  自己加上以 i-1位置结尾 的最大子数组//3.初始化 = 0 即可for (int i = 1; i <= n; i++) {f[i] = Math.max(f[i - 1] + nums[i - 1], nums[i - 1]);g[i] = Math.min(g[i - 1] + nums[i - 1], nums[i - 1]);sum += nums[i - 1];}int maxF = -0x3f3f3f3f;//统计结果int minG = 0x3f3f3f3f;//统计结果//可以和上面统一合并,一个循环就够了for (int i = 1; i <= n; i++) {maxF = Math.max(maxF,f[i]);minG = Math.min(minG,g[i]);}//为了防止全是负数返回0,所以sum - minG要和0做判断//因为  -8 - (-8) = 0;全是负数sum = -8 minG = -8 所以要返回maxFreturn Math.max(maxF,sum - minG == 0 ? maxF : sum - minG);}

3.和为k的子数组个数 

. - 力扣(LeetCode)

 思路分析:

//解法 动态规划  +  hash表   k == pre[i](i位置的前缀和) - pre[j - 1] //此时 [j,i]的子数组为k
 public int subarraySum(int[] nums, int k) {int count = 0;//统计出现了多少次int n = nums.length;HashMap < Integer, Integer > hash = new HashMap<>();//当词典使用,存储所有前缀和hash.put(0,1);//记录0出现了1次,防止前缀和单独构成答案//1.状态表示   以i位置为结尾的区间和int[] pre = new int[n + 1];//2.状态转移方程  pre[i] = pre[i - 1] + nums[i]//3.初始化  防止j - 1 越界 pre[0] = 0for (int i = 1; i <= n; i++) {pre[i] = pre[i - 1] + nums[i - 1];//下标映射,因为我的pre[0]是虚拟节点if (hash.containsKey(pre[i] - k)){count += hash.get(pre[i] - k);}hash.put(pre[i],hash.getOrDefault(pre[i],0) + 1);//键为前缀和的值 ,值为出现的次数}return count;}

 滚动数组优化形成前缀和

//因为上述我们只使用了,pre[i - 1] 和 pre[i] 这两种状态,所以可以使用滚动数组进行优化,设置两个变量即可//也就是我们熟知的前缀和public int subarraySum1(int[] nums, int k) {int count = 0;//统计出现了多少次int n = nums.length;HashMap < Integer, Integer > hash = new HashMap<>();//当词典使用,存储所有前缀和int pre = 0;hash.put(0,1);//记录0出现了1次,防止前缀和单独构成答案for (int i = 0; i < n; i++) {pre += nums[i];if (hash.containsKey(pre - k)){count += hash.get(pre - k);}hash.put(pre,hash.getOrDefault(pre,0) + 1);//键为前缀和的值 ,值为出现的次数}return count;}

4.乘积为k的最大子数组

 

. - 力扣(LeetCode)

思路分析:注释都有明确标注状态表示和转移方程

 public int maxProduct(int[] nums) {int n = nums.length;//1.定义状态表示int[] f = new int[n + 1];//以i位置为结尾  所有子数组中 乘积的最大值   遇到正数我要你int[] g = new int[n + 1];//以i位置为结尾  所有子数组中 乘积的最小值   遇到负数我要你//2.状态转移方程  遇到正数我要最大值(f[i - 1])    遇到负数我要最小值(g[i - 1])//3.初始化  防止i - 1越界但不可保存0,因为初始化的初衷就是保证后续的位置不受影响f[0] = g[0] = 1;//注意多次赋值是从右往左进行的int ret = -0x3f3f3f3f;for (int i = 1; i <= n; i++) {if (nums[i - 1] > 0){f[i] = Math.max(f[i - 1] * nums[i - 1],nums[i - 1]);g[i] = Math.min(g[i - 1] * nums[i - 1],nums[i - 1]);}else {f[i] = Math.max(g[i - 1] * nums[i - 1],nums[i - 1]);g[i] = Math.min(f[i - 1] * nums[i - 1],nums[i - 1]);}ret = Math.max(ret,f[i]);}return ret;}

5.乘积为正数的最长子数组长度

. - 力扣(LeetCode)

 public int getMaxLen(int[] nums) {int n = nums.length;int ret = 0;//统计//1.状态表示int[] f = new int[n + 1];//以i位置为结尾中的 所有子数组中的 乘积为正数的最大长度int[] g = new int[n + 1];//以i位置为结尾中的 所有子数组中的 乘积为负数的最大长度//2.状态转移方程  f[i]如果i位置为正数为 f[i - 1] + 1    负数 g[i - 1] + 1//              g[i]同理正数g[i - 1] + 1   负数 f[i - 1] + 1//3.初始化 默认长度为0不影响后续结果for (int i = 1; i <= n; i++) {if (nums[i - 1] > 0){f[i] = f[i - 1] + 1;//当最后一个元素为正数的时候,并且g[i - 1] = 0表示前面没有负数,所以不可能组成负数g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;}else if (nums[i - 1] < 0){//当最后一个元素为负数的时候,并且g[i - 1] = 0表示前面没有负数,所以不可能组成正数f[i] = g[i - 1] == 0 ? 0 : g[i - 1]  + 1;g[i] = f[i - 1] + 1;}else {//处理为0的情况f[i] = 0;g[i] = 0;}ret = Math.max(ret,f[i]);}return ret;}

总结

当解决子数组问题时,动态规划是一个强大而智能的工具。通过将问题分解成更小的子问题并以递归的方式解决它们,动态规划可以高效地找到原始问题的解。在动态规划中,我们常常会遇到两种状态:一种是单独成一段,另一种是以 i 结尾的子数组。

枚举和动态规划是解决子数组问题的两种主要方法。枚举法需要考虑所有可能的子数组组合,然后比较它们以找到最优解。而动态规划则通过保存历史记录来避免不必要的重复计算,从而提高效率。

在动态规划中,常用的技巧包括前缀和和预处理。前缀和可以帮助我们快速求出数组中任意子数组的和,而预处理则可以在问题出现之前就对数据进行处理,以提高计算效率。

综上所述,动态规划是解决子数组问题的一种强大工具,通过合理利用枚举、动态规划、前缀和和预处理等技巧,我们可以高效地解决各种复杂的算法挑战,为问题提供简单明了的解决方案。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【redis】Redis数据类型(三)List类型

目录 List类型介绍特点 List数据结构附&#xff1a;3.2以前的版本(介绍一下压缩列表和双向链表)压缩列表ZipList双向链表LinkedList 常用命令lpush示例 lpushx示例 rpush示例 rpushx示例 LPOP示例 RPOP示例 BLPOP非阻塞行为阻塞行为相同的 key 被多个客户端同时阻塞在 MULTI/EX…

爬虫学习:基本网络请求库的使用

目录 一、urllib网络库 1.urlopen()方法 2.request方法 二、requests网络请求库 1.主要方法 2.requests.get()和requests.post() 一、urllib网络库 1.urlopen()方法 语法格式&#xff1a; urlopen(url,data,timeout,cafile,capath,context) # url:地址 # data:要提交的数据…

nacos(docker部署)+springboot集成

文章目录 说明零nacos容器部署初始化配置高级配置部分访问权限控制命名空间设置新建配置文件 springboot配置nacos添加依赖编写测试controller 说明 nacos容器部署采用1Panel运维面板&#xff0c;进行部署操作&#xff0c;简化操作注意提前安装好1Panel和配置完成docker镜像加…

避雷!7.7分,新增1区TOP被标记On Hold,5本已被踢除!

本周投稿推荐 SSCI • 2/4区经管类&#xff0c;2.5-3.0&#xff08;录用率99%&#xff09; SCIE&#xff08;CCF推荐&#xff09; • 计算机类&#xff0c;2.0-3.0&#xff08;最快18天录用&#xff09; SCIE&#xff08;CCF-C类&#xff09; • IEEE旗下&#xff0c;1/2…

每天五分钟深度学习:数学中常见函数中的导数

本文重点 导数是微积分学中的一个核心概念,它描述了函数在某一点附近的变化率。在物理学、工程学、经济学等众多领域中,导数都发挥着极其重要的作用。本文旨在详细介绍数学中常见函数的导数,以期为读者提供一个全面而深入的理解。 数学中常见的导数 常数函数的导数 对于常数…

Golang | Leetcode Golang题解之第69题x的平方根

题目&#xff1a; 题解&#xff1a; func mySqrt(x int) int {if x 0 {return 0}C, x0 : float64(x), float64(x)for {xi : 0.5 * (x0 C/x0)if math.Abs(x0 - xi) < 1e-7 {break}x0 xi}return int(x0) }

如何构建用于从收据中提取信息的生成式人工智能工具

原文地址&#xff1a;how-to-build-a-generative-ai-tool-for-information-extraction-from-receipts 使用 LangChain 和 OpenAI 工具从 Google Drive 中存储的收据图像中提取结构化信息 2024 年 4 月 10 日 纸质收据有各种样式和格式&#xff0c;是自动信息提取的一个有趣目…

Spring拦截器

一、简介&#xff1a; Spring Boot 拦截器是面向切面编程-----AOP 的具体实现&#xff0c;用于对请求做预处理。 1.1.什么是拦截器&#xff1a;在AOP&#xff08;Aspect-Oriented Programming&#xff09;中用于在某个方法或字段被访问之前&#xff0c;进行拦截然后在之前或之…

FSNotes for Mac v6.7.1中文激活:轻量级笔记管理工具

FSNotes for Mac&#xff0c;一款专为Mac用户打造的轻量级笔记管理工具&#xff0c;让您的笔记管理变得简单而高效。 FSNotes for Mac v6.7.1中文激活版下载 它采用Markdown文件格式&#xff0c;让您轻松创建和编辑富文本笔记&#xff0c;无需担心格式问题。同时&#xff0c;FS…

USB-HUB带宽共享机制

一. USB2.0-HUB工作机理 1. USB2.0 HUB的结构 USB2.0支持低速&#xff08;1.5Mbps&#xff09;、全速&#xff08;12Mbps&#xff09;以及高速&#xff08;480Mbps&#xff09;三种外部设备。为了将全速/低速设备对高速设备可用带宽的影响降到最小&#xff0c;USB2.0提供了一…

基于openEuler22.03 LTS环境的docker容器基础

一、说明 本文配置环境为VMware虚拟机或华为云服务器&#xff08;4核CPU&#xff0c;8 GB内存&#xff0c;40GB磁盘&#xff09;&#xff0c;OS为openEuler 22.03 LTS &#xff0c;Linux服务器要求能联网。 二、安装docker 2.1 安装docker软件包 [rootnode01 ~]# dnf -y in…

C#图像:1.图像区域分割与提取

&#xff08;1&#xff09;创建一个名为SplitImage的窗体的应用程序&#xff0c;将窗体改名为FormSplitImage。 &#xff08;2&#xff09;创建一个名为ImageProcessingLibrary的类库程序&#xff0c;为该工程添加名为ImageProcessing的静态类 &#xff08;3&#xff09;为Imag…

数字文旅重塑旅游发展新生态:以数字化转型为契机,推动旅游产业的创新发展,提升旅游服务的智能化、网络化和个性化水平

目录 一、引言 二、数字化转型推动旅游产业创新发展 1、数字化转型提升旅游产业效率 2、数字化转型拓展旅游产业边界 3、数字化转型促进旅游产业可持续发展 三、提升旅游服务智能化、网络化和个性化水平 1、智能化提升旅游服务体验 2、网络化拓宽旅游服务渠道 3、个性…

Stable Diffusion AI绘画

我们今天来了解一下最近很火的SD模型 ✨在人工智能领域&#xff0c;生成模型一直是研究的热点之一。随着深度学习技术的飞速发展&#xff0c;一种名为Stable Diffusion的新型生成模型引起了广泛关注。Stable Diffusion是一种基于概率的生成模型&#xff0c;它可以学习数据的潜…

【GDAL应用】基于rasterstats的矢量数据分区统计栅格值信息

文章目录 1 实现效果2 实现功能3 实现代码 1 实现效果 矢量数据&#xff1a; 栅格数据&#xff1a;只有一个value值&#xff08;像素值或DN值&#xff09;&#xff0c;为1&#xff0c;计算统计时nodata作为0值处理。 输出结果&#xff1a; 2 实现功能 基于单波段的栅格数…

探索设计模式的魅力:分布式模式让业务更高效、更安全、更稳定

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;坚持默默的做事。 ✨欢迎加入探索分布式模式之旅✨ 在数字化时代&#xff0c;企业面临着前所未有的挑战和机遇。…

面试中算法(使用栈实现队列)

使用栈来模拟一个队列&#xff0c;要求实现队列的两个基本操作:入队、出队。 栈的特点&#xff1a;先入后出&#xff0c;出入元素都是在同一端&#xff08;栈顶&#xff09;。 队列的特点&#xff1a;先入先出&#xff0c;出入元素是在两端&#xff08;队头和队尾)。 分析&…

yolov8 区域声光报警+计数

yolov8 区域报警计数 1. 基础2. 报警功能2. 1声音报警代码2. 2画面显示报警代码 3. 完整代码4. 源码 1. 基础 本项目是在 yolov8 区域多类别计数 的基础上实现的&#xff0c;具体区域计数原理可见上边文章 2. 报警功能 设置一个区域region_points&#xff0c;当行人这一类别…

Microsoft Remote Desktop Beta for Mac:远程办公桌面连接工具

Microsoft Remote Desktop Beta for Mac不仅是一款远程桌面连接工具&#xff0c;更是开启远程办公新篇章的利器。 它让Mac用户能够轻松访问和操作远程Windows计算机&#xff0c;实现跨平台办公的无缝衔接。无论是在家中、咖啡店还是旅途中&#xff0c;只要有网络连接&#xff0…

【hive】transform脚本

文档地址&#xff1a;https://cwiki.apache.org/confluence/display/Hive/LanguageManualTransform 一、介绍二、实现1.脚本上传到本地2.脚本上传到hdfs 三、几个需要注意的点1.脚本名不要写全路径2.using后面语句中&#xff0c;带不带"python"的问题3.py脚本Shebang…