这几天刷了子数组系列的动态规划题目，在这里写下这篇博客，总结记录一下做这些题目的经验，同时也相当于复习。
题目一：最大子数组和
题目链接：53. 最大子数组和 - 力扣（LeetCode）
当我们看完题目，看完例题之后，发现是一个动态规划的子数组问题。
那么做动态规划问题有五步
第一步：状态表示
对于这种子数组类型的题目状态表示也就是根据经验和题目要求，经验也就是以什么什么为结尾。然后根据题目要求来写状态表示
例如上面的这道题目dp[i]表示的是以i位置为结尾的所有子数组中的最大和。
第二步：根据状态表示来写状态转移方程
这里一般就可以去分析第i个元素的状态。例如这里的dp[i]就有两种状态第一种状态也就是以i为结尾的子数组中的最大和为这个i元素本身，还有一种状态也就表示除了元素i之外还包含前面i-1元素的最大子数组和，而以i-1元素为结尾的最大子数组和就放在了dp[i-1]。然后让dp[i]在这两种状态之间选择一个最大值作为自己的状态。
dp[i] = max(dp[i-1]+nums[i],nums[i])//状态转移方程
第三步初始化
首先我们来观察状态转移方程，因为当填到dp[i]的时候需要dp[i-1]，那么如果i为0，那么i-1也就成了-1，就会出现数组的越界访问，这是不正确的。为了避免这种情况有两个方法。
第一种方法，我们在填表之前就将dp[0]自己赋值，然后让循环变量从1开始。
这里如果使用这种方法，那么我们只用将dp[0]= nums[0]就可以了，因为以0元素为结尾的子数组只有它自己一个，最大值自然也就是它自己本身了。
第二种方法，我们给我们的表创建一个虚拟节点。如下图
那么此时就不会出现越界的情况了，但是使用虚拟节点需要注意两个点。
第一：虚拟节点内的值不能影响后面填表的正确
第二：注意下标的映射关系，因为现在的dp[1]其时是以nums[0]为结尾的子数组的最大值。
这里为了保证填表的正确dp[0]初始化为0，因为此时的dp[i] 肯定就是等于nums[0]了
第四步：填表顺序
因为当我们天dp[i]的时候，是需要dp[i-1]的所以是从左往右填表
第五步：确定返回值
因为我们的dp[i]代表的是以i元素为结尾的子数组中的最大和
下面就是代码的编写：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//dp[i]代表的是以i位置为结尾的所有子数组里面的最大值
//以i位置为结尾的子数组总的来说分为两个部分，要么只有i位置，要么就是i位置加上前面的子数组
//那么dp[i] = max(dp[i-1]+nums[i],nums[i])
//创建dp表
int n = nums.size();
vector<int> dp(n+1);
//初始化，因为需要使用到i-1则可以使用虚拟节点
dp[0] = 0;//确保后面填表的正确
for(int i = 1;i<=n;i++)
{
dp[i] = max(dp[i-1]+nums[i-1],nums[i-1]);//注意dp表和原数组的映射关系
}
//最后遍历dp表找出最大值
int ret_max = -INT_MAX;
for(int i = 1;i<=n;i++)//这里不能将虚拟节点也拿去比较，假设这里的值全为负数，那么就会出现0为最大的情况（如果将虚拟节点放到比较中）
{
ret_max = max(ret_max,dp[i]);
}
return ret_max;
}
};题目二：环形子数组的最大和
题目链接：918. 环形子数组的最大和 - 力扣（LeetCode）
依旧是子数组问题。当我们读懂题目后
依旧是以上面的五步走原理
第一步:状态表示
dp[i]表示的是以i位置为结尾的子数组的最大和。
第二步：状态转移方程的书写
依旧是以最后一个i位置的字符状态为例子，状态依旧只有两种那么dp[i] = max(dp[i-1]+nums[i],nums[i])。和上面的那道题目唯一的不同点也就是子数组的寻找方法上。就以示例三来解释：
那么我们现在如何寻找示例内子串的最小值呢？很明显这又是一种新的状态，对于新的状态直接在创建一个dp表这里就创建一个dp_min表,dp_min[i],表示的就是以i为结尾的子数组的最小和。
那么dp_min[i] = min(dp_min[i-1]+nums[i],nums[i])//状态转移方程
第三步初始化
依旧是使用虚拟节点，需要注意使用虚拟节点要注意两个点
dp[0] = -INT_MAX;
dp_min[0] = INT_MAX（代表整型的最大值）。
第四步：填表顺序
肯定就是从左往右填两个表了，两个表可以分开填
第五步：返回值
假设dp表中的最大值设为ret1，以及sum（整个串的和）- （dp_min这个表中的最小值）得到的ret2
但是还有一种特殊的情况需要我们处理，假设数组为-1，-2，-3。那么此时我们求出的ret1肯定是-1，但是此时的dp_min中的最小值为-6，和sum相等sum - 最小值得到的是0，反而不正确了。所以如果sum == ret2，那就直接返回ret1。
代码：
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
//这道题目如果答案（最大子数组和）的子数组在原本数组中（不需要去前面找元素），
//那么这就是一个再nums中寻找最大子树组的问题
//如果答案不在原本nums的子数组中而是在需要往前寻找的子数组中，那么首先我们知道整个数组的和（sum）我们是能求出的
//那么只需要求出原本子数组的最小值在使用sum减去这个值，就是在环外的最大子数组和了
//求取sum
int sum = 0;
int n = nums.size();
//创建dp表
vector<int> dp(n + 1);
auto dp_min = dp;
//填表
int ret1 = -INT_MAX;
int ret2 = INT_MAX;
for (int i = 1; i <= n; i++)
{
dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);
ret1 = max(ret1, dp[i]);
dp_min[i] = min(nums[i - 1], dp_min[i - 1] + nums[i - 1]);
ret2 = min(ret2, dp_min[i]);
sum+=nums[i-1];
}
//返回答案
return sum == ret2 ? ret1 : max(ret1, sum - ret2);//注意全为负数的情况
}
};题目三：乘积为正数的最长子数组长度
题目链接：1567. 乘积为正数的最长子数组长度 - 力扣（LeetCode）
当我们将题目分析完毕之后，可以知道这道题目是动态规划的子数组问题。
既然是动态规划，那么就按照五步走
第一步：状态表示
这里我们假设dp[i]代表的是以i为结尾字符的子数组中乘积的为正数的最长长度。
第二步：状态转移方程
对于状态转移方程，我们以i位置的状态来分析。
首先i位置的值可能为正数，
既然又增加了一个g表，下面我们就要完成对g表的填写。
首先g[i]表示的是以i位置为结尾的子树组中乘积为负数的值。
f[i]表示的是以i位置为结尾的子数组中乘积为正数的值。
那么现在拥有了两个表，一个f表一个g表。
那么我们下面来分析f表和g表的状态转移方程。
下一步就是初始化了，如何初始化是使用的方法依旧是创建虚拟的节点，虚拟节点的创建需要遵循两个规则。我们再来复习一遍
首先第一点：虚拟节点的值不能影响后面填表的正确性
第二点：注意下标的映射关系。
当填f[i]表的时候，需要的是f[i-1]的值，假设我们现在要填f[1]的值也就是那么如果nums[0]为正数，那么f[i] = f[0]+1;所以此时的f[0]我们设定初始化为0。那么如果nums[0]的值为负数f[1] = g[0]+1,但是如果这么写的话f[1]就会被初始化为1，这是不正确的，因为此时的nums[0]为一个负数，f[1]应该等于0所以这里需要额外处理一下。
当填g[i]表的时候，同样也要处理一下如果nums[0]为正数，g[1] = g[0]+1,那么此时的g[1]为1，但是nums[0]是正数，g[1]应该是一个负数。
下面是第三步：填表顺序
当我们填f表的时候，需要g表，并且需要的是g[i-1]/f[i-1]，所以是从左往右，两个表必须一起填写。
第四步：确定返回值
我们需要的是乘积为正数的子数组的长度最大值为多少？，所以我们需要在f表中找出最大值，然后返回。
最后是代码
class Solution {
public:
int getMaxLen(vector<int>& nums) {
//创建两个dp表f和g
//f[i]表示的是以i位置为结尾的值为正数的子数组的最长的长度
//g[i]表示以i位置为结尾的值为负数的子数组的最长长度
//创建表
int n = nums.size();
vector<int> f(n+1);//使用了虚拟节点
auto g = f;//使用auto语句创建g表
//初始化
f[0] = g[0] = 0;//初始化虚拟节点
//填表
int ret = 0;
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;//处理特殊情况
ret = max(ret,f[i]);
}
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]);
}
else
{
continue;
}
}
//返回答案
return ret;
}
};题目四：等差数列划分
题目链接：413. 等差数列划分 - 力扣（LeetCode）
分析完题目之后，我们知道这又是一个动态规划的子数组问题。
写这道题目之前我们需要知道一个知识。
那么下面来进行动态规划题目的五步走：
第一步：状态表示
dp[i]表示的就是以i为结尾的子数组中为等差数列的数目。
第二步：状态转移方程
依旧是以i位置所处的状态来分析状态转移方程，以i为结尾的子数组大体上就分成了两类，一类就是i本身不包含前面的任何一个元素，那么就代表没有等差数列。还有一类就是i和前面的某些元素构成了等差数列。
我们一种状态一种状态的分析：如果i和前面的任何一个元素都不构成等差数列，那么dp[i] = 0;
但是如果是另外一种状态呢？那么i-2 ，i-1，和i位置的元素就会构成一个等差数列。
然后根据我们在上图得到的那个数学知识就能够知道，i位置的元素和前面的元素都是构成等差数列的
那么此时的dp[i] = dp[i-1]+1。但是这里需要注意的一点是这里+1的原因，首先我们知道dp[i]代表的是以i为结尾的子树组中等差数列的数目，dp[i-1]肯定就是以i-1为结尾的子数组中的等差数列的数目，而加的这个1其实是i-2，i-1，i这一个等差数列组合。因为其它的等差数列组合在dp[i-1]中肯定也是包含着的。
则状态转移方程也就有了
if(满足i-1，i-，i为等差数列)
dp[i] = dp[i-1]+1
else
dp[i] = 0
第三步：填表顺序
因为我们填i的时候需要的是i-1，所以这里我们需要从左往右填表
第四步返回值
因为题目要求的是我们要返回所有的等差数列的可能性，所以这里需要返回dp表中所有的值的和
最后来看代码的实现：
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
//创建dp
int n = nums.size();
vector<int> dp(n);
if(n<=2)
{
return 0;
}
//初始化
dp[0] = dp[1] = 0;
//填表
int sum = 0;
for(int i = 2;i<n;i++)
{
if(nums[i] - nums[i-1] == nums[i-1]-nums[i-2])
{
dp[i] = dp[i-1]+1;
}
else
{
dp[i] = 0;
}
sum+=dp[i];
}
return sum;//返回答案
}
};题目五：最长湍流子数组
题目链接：978. 最长湍流子数组 - 力扣（LeetCode）
这道题目如果只是查看题目所给的描述的话是很难理解的，需要结合示例来一起查看。
通过示例我们能够知道这道题目也就是要求我们给出最长的波浪数组的长度。
波浪数组的特点就是如果第一个数比第二个数大，那么第二个数一定要比第三个数小一次不断地比较下去。
接下来我们尝试一下使用动态规划地思想来解决这道题目
因为出现了子数组这个关键字，子数组的题型一般使用滑动窗口解决或者是动态规划解决比较优秀。
首先第一步：状态表示
那么我们这里根据题目的要求
设置dp[i]为以i结尾的子数组中最长湍流子数组的长度。
状态表示已经完成了。
第二步状态转移方程的书写。
那么接下来就继续分析，
情况1：i元素如果大于了i-1元素，如果此时的i-1元素也是大于了i-2元素，那么i元素就不和前面的元素构成湍流数组，那么i只能自己单独作为湍流数组的开头，即dp[i] = 1,但是如果此时i和i-1等前面的元素是构成了湍流元素那么此时的dp[i] = dp[i-1]+1,因为以i-1元素为结尾的湍流子数组的最长长度就放在dp[i-1]中加上此时的i元素也就构成了dp[i]的值。
那么情况2：i元素小于i-1元素，不要忘了即使你是小于i-1也依旧是可能构成湍流子树组的，所以分析和上面是一样。
情况三：i元素等于i-1元素，在这种情况下1dp[i]肯定是只能自己当作开头了，所以此时的dp[i]等于1。
经过上面的分析我们知道仅仅只有一个dp表是不足以完成上面的两种情况了，所以下面我们需要在创建dp表来满足我们的题目需求。
那么还要创建几个dp表呢？
这里我们只需要在创建一个表，因为根据题目，要判断我们当前的i元素是否为湍流子数组中的元素，只需要判断i-2和i-1之间的关系。
那么我们这里就重新创建两个表，并且重新定义两个表的d[i],和f[i]的表示。
这里d[i]表示为以i为结尾的子数组中最长湍流子数组的长度，并且本次i和i-1的大小关系为i大于i-1.
而f[i]表示以i为结尾的子数组中最长湍流子数组的长度，并且本次i和i-1的大小关系为i小于i-1。
这里有一个小技巧因为数组中的每一个元素都可以作为湍流子数组的开头，所以f表和d表的初始值都可以设定为1。这样的设定也可以让我们少判断一种等于的情况。
那么下面重新来写状态转移方程。
if（i大于i-1）//要构成湍流子数组肯定i-1和是要小于i-2
d[i] = f[i-1]+1;
else//原理同上
{
f[i] = dp[i-1]+1
}
第三步：填表顺序
因为填d表的时候，需要f表所以这里是两个表一起填，并且是从左往右依次填表
第四步：返回值
因为是要求我们返回最长的湍流子数组的长度，所以我们需要返回两个表中的最大值
下面是代码的书写
class Solution {
public:
int maxTurbulenceSize(vector<int>& arr) {
//创建dp表并且初始化
int n = arr.size();
if(n == 1)
{
return 1;
}
vector<int> f(n,1);//在初始化的时候就将最次的值放到f表中去f为下降趋势的表
auto g = f;//g为是上升趋势的表
int ret = 0;
for(int i = 1;i<n;i++)
{
if(arr[i-1]>arr[i])//arr[i]处于下降趋势
{
f[i] = g[i-1]+1;
//并且不用去考虑g[i] == 1因为初始化的时候，就已经写了这种情况
}
else if(arr[i-1]<arr[i])//arr[i]处于上升趋势
{
g[i] = f[i-1]+1;
}//也不用管等于的情况
ret = max(max(f[i],g[i]),ret);
}
return ret;//最后返回答案
}
};题目六：单词拆分
首先我们依旧是是要搞一个状态表示
dp[i]表示为0到i位置的字符串能否拼接。
第二步：状态转移方程的书写
如何得到dp[i]的值呢？
很简单如果0到i位置的字符可以被拼接那么dp[i]为true
否则就为false。
那么下面问题就转移到了如何判断0到i的字符串是能够被拼接的呢？
首先我们可以将字典中的字符传全部都放到一个哈希表中。
然后可以按照下图的方法
但是现在需要考虑第一次也就是没有单词的情况即我们必须将dp[0]初始化为true，因为只有dp[0]为true才会去判断0之后的元素到i位置的元素是否是字典中的元素。光看这里可能会有点难以理解，请结合下面的代码一起查看
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
string new_s = '-' + s;//手动添加一个无效字符
int n = s.size();
vector<bool> dp(n + 1);//创建dp表
int n1 = wordDict.size();
unordered_map<string, int>hash;
for (int i = 0; i < n1; i++)
{
hash[wordDict[i]]++;//使用哈希表统计word中出现的单词
}
//初始化
dp[0] = true;//这里添加了一个虚拟节点，所以下面获取tmp才是i+1
//填表
for (int i = 1; i <= n; i++)
{
int j = 0;
while (j <= i)
{
if (dp[j] == true)//假设dp[0]不为true，那么即使现在的i+1和j之间的元素已经是一个字典
//中的单词了，也会因为没有true而无法进入到这个if导致全为false的情况
{
string tmp(new_s.begin()+1 + j, new_s.begin() + i+1);//使用迭代器将tmp完成赋值
//下面是判断tmp是否出现在word中
if (hash[tmp] != 0)
{
dp[i] = true;
break;
}
}
j++;
}
}
return dp[n];
}
};题目七：环绕字符串中唯一的子字符串
题目链接：467. 环绕字符串中唯一的子字符串 - 力扣（LeetCode）
第一步依旧是状态表示：
dp[i]表示在s中以i为结尾的子串中有多少个在base中出现了。
下面是状态转移方程的书写
首先以i为结尾的子串总体来说是分成的两种第一种：
就只包含i这一个字符
那么此时的dp[i] = 1。
但是如果i和前面的元素构成的子串也在base中出现了
那么此时的dp[i] = dp[i-1]//不需要加上1因为我们这里求的是以i为结尾的子字符串中有多少个子串出现在了base中，如果i和前面的元素构成的子串在base中出现过，那么只用在以i-1为结尾的在base中出现过的子字符串的末尾加上一个i元素即可，并没有增加新的子串
那么最后以i元素为结尾的子串中在base里面出现的个数自然是上面的两个情况相加了。
请看下图：
当然dp[i-1]只有在满足了条件之后才会加上。
下面解决初始化问题
因为我们知道s中的每一个单独字符肯定是会在base中出现的，所以这里我们可以将dp数组都初始化成1，这样我们就不用考虑上图中长度为1的情况了。只用判断是否需要加上dp[i-1]即可
填表顺序
要填i的时候需要i-1的值所以是从左往右填。
返回值因为题目要求我们求的是总的子数组的个数所以最后返回dp表中所有值的和即可
但是如果不进行去重处理是会出错的因为题目中要求的是要返回不同的非空子数组在base中出现的次数，所以这里我们需要对dp数组进行去重。例如题目示例中的cac，如果按照我们的返回值,最后返回的将会是3而不是2这就是没有对第二个c进行去重的处理。
那么如何进行去重呢？这里我们可以创建一个数组大小为26.
其中0位置代表的是以a为结尾的子串出现在base的情况是最多的。
原因下图
下图都是以c为结尾的子串但是dp值大的那个子串里面肯定是包含dp值小的那种情况的。
下面是代码的实现：
class Solution {
public:
int findSubstringInWraproundString(string s) {
int n = s.size();
//创建dp表
vector<int> dp(n,1);///将dp表中每一个值都初始化为1，dp[i]代表的是以i位置为结尾的字符有多少个子串是在
//base中出现的
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};//创建一个26大小的数组,其中0代表的是以a为结尾的子串（这个子串肯定是在base中出现过的）
//因为这个是从dp表里面拿的值
for(int i = 0;i<n;i++)
{
hash[s[i]-'a'] = max(hash[s[i]-'a'],dp[i]);//这里如果s[i]为a的话-'a'得到的自然是0
}
int sum = 0;
//最后返回数组里面值的和即可
for(int i = 0;i<26;i++)
{
sum+=hash[i];
}
return sum;
}
};希望这篇文章能对你有所帮助，文章如果您觉得写的不好，请见谅。如果发现了任何错误欢迎指出。