专题二十一_动态规划_子数组系列_算法专题详细总结

news/2024/11/19 23:18:40/

目录

子数组系列问题：

1. 最⼤⼦数组和（medium）

解析：  

1.状态表达式：

2.状态转移方程：

3.初始化：

4.填表顺序：

5.返回值：

总结：

2. 环形⼦数组的最⼤和（medium）

解析：

总结：

3. 乘积最⼤⼦数组（medium）

解析：

总结：

4. 乘积为正数的最⻓⼦数组（medium）

解析：

总结：

5. 等差数列划分（medium）

解析：

总结：

6. 乘积为正数的最⻓⼦数组（medium）

解析：

总结：

7. 单词拆分（medium）

解析：

代码编写：

总结：

8. 环绕字符串中唯⼀的⼦字符串（medium）

解析：

总结：

总结不易~本章节对我有很大的收获，希望对你也是！！！

在经过前面多节动态规划的学习之后，我们对多状态动态规划问题有了更深入的体会。现在，让我们进入新的章节 —— 子数组和子序列问题。将这两小节放在一起进行对比，通过学会总结和对比，我们能够更深刻地理解其中的含义。

子数组系列问题：

1. 最⼤⼦数组和（medium）

题目意思很简单，就是要求出数组内和最大的一段子数组

解析：  

1.状态表达式：

dp[i]表示：以i位置为结尾的所有子数组和里面的最大值

2.状态转移方程：

画出dp表，可以发现所有子数组被分成了两类，一类是只以自己结尾，另一类是自己+前面的最大和子数组，那么由这两类构成一个状态转移方程： 
dp[i]=max(dp[i-1]+nums[i-1],nums[i-1]);

3.初始化：

这里添加一个虚拟节点，为了避免访问越界i-1，添加一个虚拟节点初始化为0即可，这样就算nums[0]<0是一个负值，最后dp[1]取值都是等于nums[0]

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

4.填表顺序：

由i-1 -> i 所以填表顺序就是从左往右填

5.返回值：

设置一个ret=nums[0] 返回最大值dp表内的最大值即可；
代码编写： 
class Solution {
public:int maxSubArray(vector<int>& nums) {int n=nums.size();int ret=nums[0];vector<int> dp(n+1);for(int i=1;i<=n;i++){dp[i]=max(dp[i-1]+nums[i-1],nums[i-1]);ret=max(dp[i],ret);}return ret;}
};

总结：

最大子数组和是一个十分经典的问题，一定一定要完全弄懂弄透；

2. 环形⼦数组的最⼤和（medium）

求出环形子数组里面的最大和

解析：

画图：
所以分别设置两个dp表来分别求出这个数组内的最大和最小值，然后进行判断max(sum-_min,_max) 谁最大，就返回谁
1.状态表达式：
dp[i]表示：以i位置为结尾的所有子数组的最大和
_dp[i]表示：以i位置为结尾的所有子树组的最小和
2.状态转移方程： 
_dp[i]=min(_dp[i-1]+nums[i-1],nums[i-1]);
dp[i]=max(dp[i-1]+nums[i-1],nums[i-1]);

3.初始化：
dp[0]为添加的一个虚拟节点，初始化为0即可
4.填表顺序：
从左往右
5.返回值：
返回值有点讲究，返回数组总和-_min 和 _max的最大值，如果_min==总和就说明整个数组都是负数，返回最小的负数 
return _max==_min?ret:max(ret,_max-_min);
代码编写： 
class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int n=nums.size();vector<int> dp(n+1);int ret=nums[0];int sum=0;int f=0;for(auto e : nums){if(e>0) f=1;sum+=e;  }for(int i=1;i<=n;i++){dp[i]=min(dp[i-1]+nums[i-1],nums[i-1]);ret=min(ret,dp[i]);}vector<int> _dp(n+1);int _ret=nums[0];for(int i=1;i<=n;i++){dp[i]=max(dp[i-1]+nums[i-1],nums[i-1]);_ret=max(_ret,dp[i]);}cout<<ret<<" "<<_ret<<endl;if(f==0) return _ret;return max(sum-=ret,_ret);}
};

总结：

这一题环形数组是一体很经典的题目，注意要分别对最大值进行分类讨论

3. 乘积最⼤⼦数组（medium）

求最大乘积连续子数组

解析：

这个题目其实还是很恶心人的，很多测试用例都贼恶心
1.状态表达式:
那么遇到eg：1 2 3 4 5 像这种连续的正数可以很顺利的通过
但是遇到eg：[-2,3,-4] 取最大值就只能取到3，可是最大值应该是 -2 * 3 *-4 才对
所以一个dp表只用来存最大值是不够的，还应该设置一个_dp表专门来存最小值（小于0）
就可以让dp取最大的空间变大dp[i]=max(dp[i-1]*nums[i-1],max(nums[i-1],_dp[i-1]*nums[i-1]));
dp[i]表示:以i为结尾，所有子数组最大乘积的值
_dp[i]表示：以i为结尾，所有子数组中乘积最小的值
2.状态转移方程就是： 
dp[i]=max(dp[i-1]*nums[i-1],max(nums[i-1],_dp[i-1]*nums[i-1]));
_dp[i]=min(dp[i-1]*nums[i-1],min(_dp[i-1]*nums[i-1],nums[i-1]));

3.初始化：

dp[0]一定要初始化为1，否则后面的所有值都是0，不能影响dp表后面的值

dp[0]=1,_dp[0]=1;

4.填表顺序：

从左往右

5.返回值：

返回最大的dp值，因为dp[i]表示:以i为结尾，所有子数组最大乘积的值

代码编写： 
class Solution {
public:int maxProduct(vector<int>& nums) {int n=nums.size();vector<int> dp(n+1);vector<int> _dp(n+1);dp[0]=1,_dp[0]=1;int ret=nums[0];for(int i=1;i<=n;i++){dp[i]=max(dp[i-1]*nums[i-1],max(nums[i-1],_dp[i-1]*nums[i-1]));_dp[i]=min(dp[i-1]*nums[i-1],min(_dp[i-1]*nums[i-1],nums[i-1]));ret=max(dp[i],ret);}return ret;}
};

总结：

求关于子数组乘积，从上面可以看出，一个最大dp表是不够的，还需要一个最小的dp表来表示负数，然后来扩大最大dp表的范围

4. 乘积为正数的最⻓⼦数组（medium）

题目意思很简单，就是求出最长的乘积为正数的子数组长度

解析：

1.状态表达式：
dp[i]表示：以i位置为结尾的所有子数组中乘积为正数的最长长度
但是这一题跟上一题一样，如果只有关于正数乘积的最长长度，不记录负数乘积的最长长度，就无法得出关于当前nums[i] < 0 的时候求出 _dp[i-1] * nums[i] 更长的正数乘积长度
所以还要单独设置一个_dp[i]来表示负数乘积的更长长度，这样dp[i] 的选择返回会变的更大：
_dp[i]表示：以i位置为结尾的所有子数组中乘积为负数的最长长度

2.状态转移方程：

当前位置就有两种情况可以考虑：

nums[i] > 0 --> dp[i] = dp[i-1] + 1       
 但是不能保证所有情况下，_dp[i-1]都是存在的，所以每次判断_dp[i]都要有一个前提：
                         _dp[i]=_dp[i-1]==0?0:_dp[i-1]+1;

nums[i] < 0 --> _dp[i] = dp[i-1] + 1
                      但是不能保证所有情况下，_dp[i-1]都是存在的，所以每次判断_dp[i]都要有一个提：
                         dp[i]=_dp[i-1]==0?0:_dp[i-1]+1;


3.初始化：

因为要返回的是乘积为正数的最大长度，所以我们多开一个虚拟节点，为了不会越界访问，在dp[1]这个位置跟dp[0]这个位置没有必然联系，因为dp[0]是一个多开的虚拟节点，所以dp[1]等于0 还是等于1取决于nums[1-1]本身，所以dp[0]初始化为0即可

4.填表顺序：

从左往右填

5.返回值：

返回最大的dp[i] 即可

代码编写：

class Solution {
public:int getMaxLen(vector<int>& nums) {int n=nums.size();vector<int> dp(n+1);auto _dp=dp;int ret=0;for(int i=1;i<=n;i++){if(nums[i-1]>0){dp[i]=dp[i-1]+1;_dp[i]=_dp[i-1]==0?0:_dp[i-1]+1;}else if(nums[i-1]<0){dp[i]=_dp[i-1]==0?0:_dp[i-1]+1;_dp[i]=dp[i-1]+1;}else dp[i]=_dp[i]=0;ret=max(ret,dp[i]);}return ret;}
};

总结：

这一题跟上一题很类似，具体还是要单独来分析每一种情况，只要在草稿纸上分析透彻了就大差不差了，首先就是分析当前dp[i]格子可以遇到几种情况，会遇到前一个值的乘积可能大于0 可能小于0，在考虑当前格子的nums[i]是大于0 还是小于0 ，这样一排列组合 就有4种情况

5. 等差数列划分（medium）

题意很简单，就是求出这个数组内所有的等差数列的个数

解析：

1.状态表达式：

dp[i]表示：以i位置为结尾的所有子数组满足等差数列的数组的个数

2.状态转移方程：

条件：nums[i] + nums[i-2] == 2*nums[i-1]
才能满足是等差数列
eg:      1  2  3  4  5
下标：0  1  2  3  4
dp[2] = 1 , dp[3] = 2 , dp[4] = 3
也就是说dp[i] = dp[i-1] + 1;

3.初始化：

因为是求关于等差数列的个数，所以只有满足条件才能 +1 所以这一题不用多开虚拟节点，并且全部都初始化为0即可

4.填表顺序：

从左往右填

5.返回值：

因为每一个i位置为结尾都是一个独立的情况，所以要设置ret += 所有的dp[i]

代码编写：

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n=nums.size();if(n<3) return 0;vector<int> dp(n);int ret=0;for(int i=2;i<n;i++){if(nums[i-2] + nums[i] == 2*nums[i-1]) dp[i] = dp[i-1] + 1;ret+=dp[i];}return ret;}
};

总结：

这一题只用设置一个dp表，只用分析当前位置的3个数字是否满足等差的情况，如果满足就可以跟dp[i-1]联动起来，因为dp[i-1]满足的，dp[i]也会满足

6. 乘积为正数的最⻓⼦数组（medium）

题目意思就是要满足：
(nums[i]>nums[i-1]&&nums[i-2]>nums[i-1]) || (nums[i]<nums[i-1]&&nums[i-2]<nums[i-1])
这样交错式的就是一个湍流子数组，要返回最长的这种子数组的长度

解析：

1.状态表达式：
dp[i]表示：以i位置为结尾的湍流子数组的最长长度
2.状态转移方程：
因为返回的是最长长度，所以每次都只是在满足dp[i-1]条件下，长度+1，所以这一题主要就是要分析在什么情况下+1

条件：nums[i] < nums[i-1]&&nums[i-2] < nums[i-1] 下满足先升后降

条件：nums[i] > nums[i-1]&&nums[i-2] > nums[i-1] 下满足先降后升

只有在这种条件下才能满足dp[i] = dp[i-1] + 1


细节问题：
最后就是不满足任何一种情况，那么dp[i]就只能置为1本身的长度了
3.初始化：
这一题不用多开空间，但是要访问dp[i] dp[i-1] dp[i-2] 三个位置的值，其中最远的就是i-2，所以为了避免越界，要提前处理好nums.size()==2的情况，开始都将dp[0] = dp[1] =1
如果有nums[0] != nums[1] 就说明dp[1]=2，初始化长度为2
4.填表顺序：
从左往右填表
5.返回值：
设置一个ret，返回dp[i] 里面的最大值
编写代码： 
class Solution {
public:int maxTurbulenceSize(vector<int>& nums) {int n=nums.size();if(n==1) return 1;vector<int> dp(n);dp[0]=dp[1]=1;if(nums[1]!=nums[0]) dp[1]=2;if(n==2) return dp[1];int ret=0;for(int i=2;i<n;i++){if((nums[i]>nums[i-1]&&nums[i-2]>nums[i-1]) || (nums[i]<nums[i-1]&&nums[i-2]<nums[i-1]))dp[i] = dp[i-1] + 1;else if((nums[i]>nums[i-1]&&nums[i-2]<=nums[i-1]) || (nums[i]<nums[i-1]&&nums[i-2]>=nums[i-1]))dp[i] = 2;else dp[i] = 1;cout<<dp[i]<<endl;ret=max(ret,dp[i]);}return ret;}
};

总结：

这一题的细节情况较多，只要能在草稿纸上画图耐心分析，一定可以考虑到所有的情况的！

7. 单词拆分（medium）

题目意思很简单，就是给了一个字典，然后可以多次使用里面的单词，返回能否拼接成字符串s

解析：

1.状态表达式：
dp[i]表示：以i位置为结尾的[0,i]区间的字符串，能否被拼接，所以dp是一个bool类型的数组
2.状态转移方程：

if(dp[j-1]&&hash.count(str)) dp[i]=true;

判断条件：
在保证前面的字符串能够被拼接的条件下[0,j-1]，还要保证最后一个单词在字典里面存在[j,i]
3.初始化:
由于最后dp[i] 跟 dp[j-1] 有关，j --> [0,i] 所以为了防止越界访问，可以多开一个虚拟节点
然后填入true，dp[0]=true,为了不影响后续的填表正确
4.填表顺序：
从左往右
5.返回值：
返回dp[n],表示以n位置为结尾的字符串能否被拼接

代码编写：

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int n=s.size();unordered_map<string,int> hash;for(auto e : wordDict) hash[e]++;vector<bool> dp(n+1);dp[0]=true;//保证后续填表是正确的for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){string str=s.substr(j-1,i-j+1);if(dp[j-1]&&hash.count(str)) dp[i]=true;}}return dp[n];}
};

总结：

这一题真的有点难度，一定要吃透才行，如果没见过这个体型，那这次记住了就直接套模板了

8. 环绕字符串中唯⼀的⼦字符串（medium）

题目意思很简单，就是在[a-z-a]这个连续的字符串内找到字符串s有多少个字串在这里面存在

解析：

1.状态表达式：

dp[i]表示：以i位置为结尾的字符串中的子串在环绕字符串中存在的个数
2.状态转移方程：
判断条件：
要满足s[i-1] + 1 =s[i] || s[i-1] == 'z' && s[i] == 'a' 即可dp[i] += dp[i-1]
因为此时的dp[i]满足条件只是满足的子串长度变长了，并不是个数变多了
3.初始化：
所有dp[i]=1 都初始化为1，表示每一个字符都是可以单独在环绕字符里面存在的
4.填表顺序：
从左往右填
5.返回值：
eg:cbc这个字符串，就会存在 'c' 'cb' 'b' 三种情况，而多出来的一个'c'则不记录
创建一个26大小的hash表白，里面只存放以某一个字符结尾的子串的最多存在的子串个数，因为长子串必定包含短子串
最后返回hash表内的所有和
代码编写： 
class Solution {
public:int findSubstringInWraproundString(string s) {int n=s.size();vector<int> dp(n,1);for(int i=1;i<n;i++)if(s[i-1]+1==s[i] || s[i-1]=='z'&&s[i]=='a') dp[i]+=dp[i-1];int hash[26]={0};for(int i=0;i<n;i++)hash[s[i]-'a']=max(hash[s[i]-'a'],dp[i]);int ret=0;for(auto e : hash) ret+=e;return ret;    }
};

总结：

这一题的细节问题很多，还需要自己下去多思考多总结，总之动态规划问题千变万变，兜离不开以i位置为结尾的元素个数/长度，然后考虑判断条件，来确定状态转移方程，最后就思考细节问题即可，这一题就是要考虑长子串 遇到短子串会有包含关系

总结不易~本章节对我有很大的收获，希望对你也是！！！


http://www.ppmy.cn/news/1548349.html

相关文章

Comfy UI Manager 自定义节点管理

Comfy UI Manager 自定义节点管理

在 Stable Diffusion Web UI 中&#xff0c;可以通过插件的方式&#xff0c;扩展更多的功能&#xff0c;如&#xff1a;tagger提示词反推、ControlNet 等。 同样的在 Comfy UI 中有类似的功能实现&#xff0c;不过在 Comfy UI 中叫做自定义节点。 通过安装自定义节点的方式&a…
阅读更多...
Golang | Leetcode Golang题解之第564题寻找最近的回文数

Golang | Leetcode Golang题解之第564题寻找最近的回文数

题目&#xff1a; 题解&#xff1a; func nearestPalindromic(n string) string {m : len(n)candidates : []int{int(math.Pow10(m-1)) - 1, int(math.Pow10(m)) 1}selfPrefix, _ : strconv.Atoi(n[:(m1)/2])for _, x : range []int{selfPrefix - 1, selfPrefix, selfPrefix …
阅读更多...
Spring Security 认证

Spring Security 认证

Spring Security 是一个功能强大的安全框架&#xff0c;广泛用于保护 Java 应用程序。它提供了多种认证和授权机制&#xff0c;以确保应用程序的安全性。以下是认证过程的详细概述以及几种常见的认证方式。 认证过程概述 用户凭证提交&#xff1a; 用户通过登录表单提交用户名…
阅读更多...
外包干了2个月，技术明显退步

外包干了2个月，技术明显退步

回望过去&#xff0c;我是一名普通的本科生&#xff0c;于2019年通过校招有幸加入了南京某知名软件公司。那时的我&#xff0c;满怀着对未来的憧憬和热情&#xff0c;投入到了功能测试的岗位中。日复一日&#xff0c;年复一年&#xff0c;转眼间&#xff0c;我已经在这个岗位上…
阅读更多...
SpringBoot（二十三）SpringBoot集成JWT

SpringBoot（二十三）SpringBoot集成JWT

最近整理完docker之后&#xff0c;突然想到&#xff0c;我是不是可以使用docker部署多个blog实例&#xff0c;来实现一下负载均衡呢&#xff1f; 现阶段&#xff0c;blog项目使用的是SESSION来做用户登录信息存储&#xff0c;如果配置负载均衡的话&#xff0c;那session其实就不…
阅读更多...
Javaweb-day13事务管理AOP

Javaweb-day13事务管理AOP

spring的事务管理&spring框架的第二大核心AOP面向切面编程 spring框架的第一大核心是前面讲的IOC控制反转 事务管理 事务回顾 概念&#xff1a;事务是一组操作的集合&#xff0c;它是一个不可分割的工作单位&#xff0c;这些操作要么同时成功&#xff0c;要么同时失败。…
阅读更多...
动手学深度学习69 BERT预训练

动手学深度学习69 BERT预训练

1. BERT 3亿参数 30亿个词 在输入和loss上有创新 两个句子拼起来放到encoder–句子对 cls-class分类 sep-seperate 分隔符 分开每个句子 告诉是哪个句子 两个句子给不同的向量 位置编码不用sin cos&#xff0c; 让网络自己学习 bert–通用任务 encoder 是双向的&#xff0c;…
阅读更多...
前端项目接入单元测试手册

前端项目接入单元测试手册

一、单元测试 Vue.js项目中的单元测试是一种软件测试方法&#xff0c;通过对最小的、可测试的代码单元进行检查和验证来保证代码质量。确保每个组件作为独立单元正确执行其预定功能。当代码库随着时间发展增长时&#xff0c;单元测试成为识别错误和避免潜在问题的关键手段。此…
阅读更多...
最新文章

Copyright @ 2022~2023