动态规划＜五＞ 子数组问题(含对应LeetcodeOJ题)
目录
引例
经典LeetcodeOJ题
1.第一题
2.第二题
3.第三题
4.第四题
5.第五题
6.第六题
7.第七题
引例
OJ传送门 Leetcode<53> 最大子数组和
画图分析:
使用动态规划解决
1.状态表示
dp[i]表示以i位置为结尾的所有子数组中的最大和
2.状态转移方程
子数组的问题可以根据最近的一步划分为长度为1和长度大于1这两种情况
3.初始化
根据状态转移方程，可能会访问越界的为i=0时，这里使用添加一个虚拟节点的方式来初始化
根据上面的dp表示，dp[0]的值应该是nums[0]，那么为了不影响dp[0],此时dp[0-1]初始化为0，在多添加一个节点后，即dp[0-1+1]=0
往后在计算时要注意下标的映射关系
4.填表顺序 从左往右
5.返回值 因为求解的为子串，可能会以任意一个位置结束
所以返回值是整个dp表中的最大值
具体代码:
int maxSubArray(vector<int>& nums)
{
int n=nums.size();
vector<int> dp(n+1);
int ret=INT_MIN;
for(int i=1;i<=n;++i)
{
dp[i]=max(nums[i-1],nums[i-1]+dp[i-1]);//注意下标的映射关系
ret=max(ret,dp[i]);
}
return ret;
}经典LeetcodeOJ题
1.第一题
OJ传送门 Leetcode<53> 环形子数组的最大和
画图分析:
使用动态规划解决
1.状态表示
f[i]表示以i位置为结尾的所有子数组中的最大和
g[i]表示以i位置为结尾的所有子数组中的最小和
2.状态转移方程
和上面例题一样进行分析
3.初始化
和上面例题一样，添加一个虚拟节点来完成初始化，虚拟节点值为0
4.填表顺序 从左往右
5.返回值
具体代码:
int maxSubarraySumCircular(vector<int>& nums)
{
int n=nums.size(),sum=0;
for(auto x:nums) sum+=x;
vector<int> f(n+1),g(n+1);
int fmax=INT_MIN,gmin=INT_MAX;
for(int i=1;i<=n;++i)
{
f[i]=max(nums[i-1],nums[i-1]+f[i-1]);
g[i]=min(nums[i-1],nums[i-1]+g[i-1]);
fmax=max(fmax,f[i]);
gmin=min(gmin,g[i]);
}
return sum==gmin? fmax:max(fmax,sum-gmin);
}2.第二题
OJ传送门 Leetcode<152> 乘积最大子数组
画图分析:
使用动态规划来解决
1.状态表示---根据经验(以xx位置为结尾，xxxx)+题目要求
dp[i]表示以i位置为结尾的所有子数组中的最大乘积
此时来分析状态转移方程的话，就会发现当nums[i]<0时，在前面需要求的是最小乘积
当nums[i]>0时，在前面求的是最大乘积，此时状态表示显然不能支持，就需要多加一维或者分开写
f[i]表示以i位置为结尾的所有子数组中的最大乘积
g[i]表示以i位置为结尾的所有子数组中的最小乘积
2.状态转移方程 不用考虑nums[i]=0的情况，选择0的话，乘积也都是0，在vector初始化是本来都是0
3.初始化--增加一个虚拟节点
根据状态表示及状态转移方程分析，将f[0]=g[0]=1
4.填表顺序 从左往右
5.返回值 f表中的最大值
具体代码：
int maxProduct(vector<int>& nums)
{
int n=nums.size();
vector<int> f(n+1),g(n+1);
f[0]=g[0]=1;
int ret=INT_MIN;
for(int i=1;i<=n;++i)
{
int x=nums[i-1],y=g[i-1]*nums[i-1],z=f[i-1]*nums[i-1];
f[i]=max(x,max(y,z));
g[i]=min(x,min(y,z));
ret=max(ret,f[i]);
}
return ret;
}3.第三题
OJ传送门 Leetcode<1567> 乘积为正数的最长子数组长度
画图分析:
使用动态规划解决
1.状态表示 nums[i]可正可负，求子数组的积或和所以一般是要定两个状态
f[i]表示以i位置为结尾的所有子数组中乘积为正数的最长长度
g[i]表示以i位置为结尾的所有子数组中乘积为负数的最长长度
2.状态转移方程
3.初始化----添加一个虚拟节点来辅助初始化
分析状态表示及状态转移方程，f[0],g[0]进行判断，因此填的值都为0
4.填表顺序 从左往右
5.返回值 f表中的最大值
具体代码：
int getMaxLen(vector<int>& nums)
{
int n=nums.size();
vector<int> f(n+1),g(n+1);
int ret=INT_MIN;
for(int i=1;i<=n;++i)
{
if(nums[i-1]>0)
{
f[i]=f[i-1]+1;
g[i]=g[i-1]==0? 0:g[i-1]+1;
}
else if(nums[i-1]<0)
{
f[i]=g[i-1]==0? 0:g[i-1]+1;
g[i]=f[i-1]+1;
}
ret=max(ret,f[i]);//更新结果
}
return ret;
}4.第四题
OJ传送门 Leetcode<413> 等差数列划分
画图分析:
使用动态规划解决
1.状态表示 -----经验+题目要求
dp[i]表示以i结尾的所有子数组中有多少个等差数列
2.状态转移方程
先补充一个小知识，若a,b,c,d,e是等差数列，在e的后面添加元素f,f与e的之差和前面的任意两个元素的差相等，此时就能说明，a,b,c,d,e,f成等差数列
3.初始化
根据状态转移方程及状态表示，可以将dp[0],dp[1]进行初始化，因为构成等差数列的最少元素为3个，因此dp[0]=dp[1]=0
4.填表顺序 从左往右
5.返回值 因为题目求的为等差数组的个数，因此结尾位置不确定，得统计整个dp表
具体代码 ：
int numberOfArithmeticSlices(vector<int>& nums)
{
int n=nums.size();
vector<int> dp(n);
int sum=0;
for(int i=2;i<n;++i)
{
dp[i]=nums[i-1]-nums[i]==nums[i-2]-nums[i-1]? dp[i-1]+1:0;
sum+=dp[i];
}
return sum;
}5.第五题
OJ传送门 Leetcode<978> 最长湍流子数组
画图分析：
使用动态规划解决
1.状态表示
dp[i]表示以i位置为结尾的所有子数组中，最长的湍流子数组的长度
但在以最近的一步来划分子问题时，会发现nums[i]与nums[i-1]的大小关系有三种
但要形成湍流数组的话，就需要以nums[i-1]为结尾时的状态是上升还是下降的
这就说明一个状态不能解决问题，就需要再创建一个状态来表示
f[i]表示以i位置元素为结尾的所有子数组中，最后呈现"上升" 状态的湍流子数组的最大长度
g[i]表示以i位置元素为结尾的所有子数组中，最后呈现"下降" 状态的湍流子数组的最大长度
2.状态转移方程--根据nums[i]与nums[i-1]的大小关系分开处理
3.初始化
可能会发生越界的为g[0],f[0]这时根据题意及状态表示，自己一个元素即可以是上升也可以是下降的，因此初始化为1，为了简化状态转移方程来填dp表，可以将dp数组中的元素都初始化为1，这时就不用考虑很多情况了
4.填表顺序 从左往右，两个表一起填
5.返回值 求的是最长湍流数组的长度，最后一个位置的状态不一定是上升还是下降的，因此返回指的是f,g两个表中的最大值
具体代码：
int maxTurbulenceSize(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)
{
if(nums[i-1]<nums[i]) f[i]=g[i-1]+1;
else if(nums[i-1]>nums[i]) g[i]=f[i-1]+1;
ret=max(ret,max(f[i],g[i]));
}
return ret;
}6.第六题
OJ传送门 Leetcode<139> 单词拆分
画图分析：
使用动态规划解决
1.状态表示
dp[i]表示[0,i]区间的最长子串，能否被字典中的单词拼接而成
2.状态转移方程 以最近的一步来划分问题
3.初始化
当j=0时，说明整个字符串都被当成最后一个单词了，若单词在字典中，其结果为true
为方便初始化，可以添加一个虚拟的节点，在字符串中的话，就可以在头部拼接一个字符
4.填表顺序 从左往右
5.返回值 dp[n]
具体代码：
bool wordBreak(string s, vector<string>& wordDict)
{
//先做一个优化
unordered_set<string> hash;
for(auto& str:wordDict) hash.insert(str);
int n=s.size();
vector<bool> dp(n+1);
dp[0]=true;//保证后续的填表时正确的
s='-'+s;//是原始字符串的下标统一+1
for(int i=1;i<=n;++i)
{
for(int j=i;j>=1;--j)//最后一个单词的起始位置
{
if(dp[j-1]&& hash.count(s.substr(j,i-j+1)))
{
dp[i]=true;
break;
}
}
}
return dp[n];
}7.第七题
OJ传送门 Leetcode<467> 环绕字符串中唯一的子字符串
画图分析：
使用动态规划解决
1.状态表示
dp[i]表示以i位置元素为结尾的所有子串，在base中出现的个数
2.状态表示
3.初始化
根据题意及状态表示，每个字符都是会出现的，结果都是1，因此可以将dp表全部初始化为1
4.填表顺序 从左往右
5.返回值 此处应该注意重复结果的去重
如示例中的第二个cac,若直接返回dp表的和的话，就会错误
此时可以举个例子来分析一下
具体代码:
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]=='a'&& s[i-1]=='z'))
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 sum=0;
for(auto x:hash) sum+=x;
return sum;
}