专题四：子数组、子串系列

置顶 დ旧言~

已于 2024-12-17 21:29:20 修改

阅读量1k

点赞数 68

分类专栏：动态规划算法文章标签：推荐算法动态规划算法 leetcode

于 2024-12-15 19:31:32 首次发布

本文链接：https://blog.csdn.net/AAlykk/article/details/144484420

版权

动态规划算法专栏收录该内容

10 篇文章

订阅专栏

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：了解什么是记忆化搜索，并且掌握记忆化搜索算法。

> 毒鸡汤：有些事情，总是不明白，所以我不会坚持。早安!

> 专栏选自：动态规划算法_დ旧言~的博客-CSDN博客

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

一、算法讲解

动态规划（Dynamic Programming）算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法：

动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上）。

【Tips】动态规划算法解决问题的分类：

计数：有多少种方式走到右下角 / 有多少种方法选出k个数使得和是 sum。
求最大值/最小值：从左上角走到右下角路径的最大数字和最长上升子序列长度。
求存在性：取石子游戏，先手是否必胜 / 能不能取出 k 个数字使得和是 sum。

【Tips】动态规划dp算法一般步骤：

确定状态表示（dp[ i ] 的含义是什么，来源：1、题目要求；2、经验+题目要求；3、分析问题时发现重复子问题）
状态转移方程（可求得 dp[ i ] 的数学公式，来源：题目要求+状态表示）
初始化（dp 表中特别的初始值，保证填 dp 表时不会越界，来源：题目要求+状态表示）
填表顺序（根据状态转移方程修改 dp[ i ] 的方式，来源：题目要求+状态表示）
返回值（题目求解的结果，来源：题目要求+状态表示）

二、算法习题

2.1 第一题

题目链接：53. 最大子数组和 - 力扣（LeetCode）

题目描述：

算法思路：

1. 状态表⽰：

dp[i] 表⽰：以 i 位置元素为结尾的「所有⼦数组」中和的最⼤和。

2. 状态转移⽅程：

dp[i] 的所有可能可以分为以下两种：

⼦数组的⻓度为 1 ：此时 dp[i] = nums[i] ；
⼦数组的⻓度⼤于 1 ：此时 dp[i] 应该等于以 i - 1 做结尾的「所有⼦数组」中和的最⼤值再加上nums[i] ，也就是 dp[i - 1] + nums[i] 。

由于我们要的是「最⼤值」，因此应该是两种情况下的最⼤值，因此可得转移⽅程：

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

3. 初始化：

可以在最前⾯加上⼀个「辅助结点」，帮助我们初始化。使⽤这种技巧要注意两个点：

辅助结点⾥⾯的值要「保证后续填表是正确的」；
「下标的映射关系」。
在本题中，最前⾯加上⼀个格⼦，并且让 dp[0] = 0 即可。

4. 填表顺序：

根据「状态转移⽅程」易得，填表顺序为「从左往右」。

5. 返回值：

状态表⽰为「以 i 为结尾的所有⼦数组」的最⼤值，但是最⼤⼦数组和的结尾我们是不确定的。因此我们需要返回整个 dp 表中的最⼤值。

代码呈现：

class Solution {
public:
    int maxSubArray(vector<int>& nums) 
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        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], dp[i - 1] + nums[i - 1]);
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

2.2 第二题

题目链接：918. 环形子数组的最大和 - 力扣（LeetCode）

题目描述：

算法思路：

本题与「最⼤⼦数组和」的区别在于，考虑问题的时候不仅要分析「数组内的连续区域」，还要考虑「数组⾸尾相连」的⼀部分。结果的可能情况分为以下两种：

结果在数组的内部，包括整个数组；
结果在数组⾸尾相连的⼀部分上。

其中，对于第⼀种情况，我们仅需按照「最⼤⼦数组和」的求法就可以得到结果，记为 fmax 。对于第⼆种情况，我们可以分析⼀下：

如果数组⾸尾相连的⼀部分是最⼤的数组和，那么数组中间就会空出来⼀部分；
因为数组的总和 sum 是不变的，那么中间连续的⼀部分的和⼀定是最⼩的；

因此，我们就可以得出⼀个结论，对于第⼆种情况的最⼤和，应该等于 sum - gmin ，其中gmin 表⽰数组内的「最⼩⼦数组和」。两种情况下的最⼤值，就是我们要的结果。
但是，由于数组内有可能全部都是负数，第⼀种情况下的结果是数组内的最⼤值（是个负数），第⼆种情况下的 gmin == sum ，求的得结果就会是 0 。若直接求两者的最⼤值，就会是 0 。但是实际的结果应该是数组内的最⼤值。对于这种情况，我们需要特殊判断⼀下。
由于「最⼤⼦数组和」的⽅法已经讲过，这⾥只提⼀下「最⼩⼦数组和」的求解过程，其实与「最⼤⼦数组和」的求法是⼀致的。⽤ f 表⽰最⼤和， g 表⽰最⼩和。

1. 状态表⽰：

g[i] 表⽰：以 i 做结尾的「所有⼦数组」中和的最⼩值。

2. 状态转移⽅程：

g[i] 的所有可能可以分为以下两种：

i. ⼦数组的⻓度为 1 ：此时 g[i] = nums[i] ；
ii. ⼦数组的⻓度⼤于 1 ：此时 g[i] 应该等于以 i - 1 做结尾的「所有⼦数组」中和的最⼩值再加上 nums[i] ，也就是 g[i - 1] + nums[i] 。

由于我们要的是最⼩⼦数组和，因此应该是两种情况下的最⼩值，因此可得转移⽅程：

g[i] = min(nums[i], g[i - 1] + nums[i]) 。

3. 初始化：

可以在最前⾯加上⼀个辅助结点，帮助我们初始化。使⽤这种技巧要注意两个点：

辅助结点⾥⾯的值要保证后续填表是正确的；
下标的映射关系。
在本题中，最前⾯加上⼀个格⼦，并且让 g[0] = 0 即可。

4. 填表顺序：

根据状态转移⽅程易得，填表顺序为「从左往右」。

5. 返回值：

先找到 f 表⾥⾯的最⼤值 -> fmax ；
找到 g 表⾥⾯的最⼩值 -> gmin ；
统计所有元素的和 -> sum ；
返回 sum == gmin ? fmax : max(fmax, sum - gmin) 。

代码呈现：

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) 
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        int fmax = INT_MIN, gmin = INT_MAX, sum = 0;
        for (int i = 1; i <= n; i++) 
        {
            int x = nums[i - 1];
            f[i] = max(x, x + f[i - 1]);
            fmax = max(fmax, f[i]);
            g[i] = min(x, x + g[i - 1]);
            gmin = min(gmin, g[i]);
            sum += x;
        }
        return sum == gmin ? fmax : max(fmax, sum - gmin);
    }
};

2.3 第三题

题目链接：152. 乘积最大子数组 - 力扣（LeetCode）

题目描述：

算法思路：

这道题与「最⼤⼦数组和」⾮常相似，我们可以效仿着定义⼀下状态表⽰以及状态转移：

dp[i] 表⽰以 i 为结尾的所有⼦数组的最⼤乘积，
dp[i] = max(nums[i], dp[i - 1] * nums[i]) ；

由于正负号的存在，我们很容易就可以得到，这样求 dp[i] 的值是不正确的。因为 dp[i -1] 的信息并不能让我们得到 dp[i] 的正确值。⽐如数组 [-2, 5, -2] ，⽤上述状态转移得到的 dp数组为 [-2, 5, -2] ，最⼤乘积为 5 。但是实际上的最⼤乘积应该是所有数相乘，结果为 20 。

究其原因，就是因为我们在求 dp[2] 的时候，因为 nums[2] 是⼀个负数，因此我们需要的是「 i - 1位置结尾的最⼩的乘积（-10）」，这样⼀个负数乘以「最⼩值」，才会得到真实的最⼤值。

因此，我们不仅需要⼀个「乘积最⼤值的 dp 表」，还需要⼀个「乘积最⼩值的 dp 表」。

1. 状态表⽰：

f[i] 表⽰：以 i 结尾的所有⼦数组的最⼤乘积，
g[i] 表⽰：以 i 结尾的所有⼦数组的最⼩乘积。

2. 状态转移⽅程：

对于 f[i] ，也就是「以 i 为结尾的所有⼦数组的最⼤乘积」，对于所有⼦数组，可以分为下⾯三种形式：

⼦数组的⻓度为 1 ，也就是 nums[i] ；
⼦数组的⻓度⼤于 1 ，但 nums[i] > 0 ，此时需要的是 i - 1 为结尾的所有⼦数组的最⼤乘积 f[i -1] ，再乘上 nums[i] ，也就是 nums[i] * f[i - 1] ；
⼦数组的⻓度⼤于 1 ，但 nums[i] < 0 ，此时需要的是 i - 1 为结尾的所有⼦数组的最⼩乘积 g[i -1] ，再乘上 nums[i] ，也就是 nums[i] * g[i - 1] ；

（如果 nums[i] = 0 ，所有⼦数组的乘积均为 0 ，三种情况其实都包含了）

综上所述， f[i] = max(nums[i], max(nums[i] * f[i - 1], nums[i] * g[i -1]) )。

对于 g[i] ，也就是「以 i 为结尾的所有⼦数组的最⼩乘积」，对于所有⼦数组，可以分为下⾯三种形式：

⼦数组的⻓度为 1 ，也就是 nums[i] ；
⼦数组的⻓度⼤于 1 ，但 nums[i] > 0 ，此时需要的是 i - 1 为结尾的所有⼦数组的最⼩乘积 g[i --1] ，再乘上 nums[i] ，也就是 nums[i] * g[i - 1] ；
⼦数组的⻓度⼤于 1 ，但 nums[i] < 0 ，此时需要的是 i - 1 为结尾的所有⼦数组的最⼤乘积 f[i --1] ，再乘上 nums[i] ，也就是 nums[i] * f[i - 1] ；

综上所述， g[i] = min(nums[i], min(nums[i] * f[i - 1], nums[i] * g[i -1])) 。

（如果 nums[i] = 0 ，所有⼦数组的乘积均为 0 ，三种情况其实都包含了）

3. 初始化：

可以在最前⾯加上⼀个辅助结点，帮助我们初始化。使⽤这种技巧要注意两个点：

辅助结点⾥⾯的值要保证后续填表是正确的；
下标的映射关系。
在本题中，最前⾯加上⼀个格⼦，并且让 f[0] = g[0] = 1 即可。

4. 填表顺序：

根据状态转移⽅程易得，填表顺序为「从左往右，两个表⼀起填」。

5. 返回值：

返回 f 表中的最⼤值。

代码呈现：

class Solution {
public:
    int maxProduct(vector<int>& nums) 
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        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 = f[i - 1] * nums[i - 1], z = g[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;
    }
};

2.4 第四题

题目链接：1567. 乘积为正数的最长子数组长度 - 力扣（LeetCode）

题目描述：

算法思路：

状态表⽰： dp[i] 表⽰「所有以 i 结尾的⼦数组，乘积为正数的最⻓⼦数组的⻓度」。

思考状态转移：对于 i 位置上的 nums[i] ，我们可以分三种情况讨论：

如果 nums[i] = 0 ，那么所有以 i 为结尾的⼦数组的乘积都不可能是正数，此时dp[i] = 0 ；
如果 nums[i] > 0 ，那么直接找到 dp[i - 1] 的值（这⾥请再读⼀遍 dp[i -1] 代表的意义，并且考虑如果 dp[i - 1] 的结值是 0 的话，影不影响结果），然后加⼀即可，此时 dp[i] = dp[i - 1] + 1 ；
如果 nums[i] < 0 ，这时候你该蛋疼了，因为在现有的条件下，你根本没办法得到此时的最⻓⻓度。因为乘法是存在「负负得正」的，单单靠⼀个 dp[i - 1] ，我们⽆法推导出 dp[i] 的值。

但是，如果我们知道「以 i - 1 为结尾的所有⼦数组，乘积为负数的最⻓⼦数组的⻓度」 neg[i - 1]，那么此时的 dp[i] 是不是就等于 neg[i - 1] + 1 呢？

通过上⾯的分析，我们可以得出，需要两个 dp 表，才能推导出最终的结果。不仅需要⼀个「乘积为正数的最⻓⼦数组」，还需要⼀个「乘积为负数的最⻓⼦数组」。

1. 状态表⽰：

f[i] 表⽰：以 i 结尾的所有⼦数组中，乘积为「正数」的最⻓⼦数组的⻓度；
g[i] 表⽰：以 i 结尾的所有⼦数组中，乘积为「负数」的最⻓⼦数组的⻓度。

2. 状态转移⽅程：

对于 f[i] ，也就是以 i 为结尾的乘积为「正数」的最⻓⼦数组，根据 nums[i] 的值，可以分三种情况：

nums[i] = 0 时，所有以 i 为结尾的⼦数组的乘积都不可能是正数，此时 f[i] =0 ；
nums[i] > 0 时，那么直接找到 f[i - 1] 的值（这⾥请再读⼀遍 f[i - 1] 代表的意义，并且考虑如果 f[i - 1] 的结值是 0 的话，影不影响结果），然后加⼀即可，此时 f[i] = f[i - 1] + 1 ；
nums[i] < 0 时，此时我们要看 g[i - 1] 的值（这⾥请再读⼀遍 g[i - 1] 代表的意义。因为负负得正，如果我们知道以 i - 1 为结尾的乘积为负数的最⻓⼦数组的⻓度，加上 1 即可），根据 g[i - 1] 的值，⼜要分两种情况：

1. g[i - 1] = 0 ，说明以 i - 1 为结尾的乘积为负数的最⻓⼦数组是不存在的，⼜因为 nums[i] < 0 ，所以以 i 结尾的乘积为正数的最⻓⼦数组也是不存在的，此时 f[i] = 0 ；
2. g[i - 1] != 0 ，说明以 i - 1 为结尾的乘积为负数的最⻓⼦数组是存在的，⼜因为 nums[i] < 0 ，所以以 i 结尾的乘积为正数的最⻓⼦数组就等于 g[i -1] + 1 ；

综上所述， nums[i] < 0 时， f[i] = g[i - 1] == 0 ? 0 : g[i - 1] +1;

对于 g[i] ，也就是以 i 为结尾的乘积为「负数」的最⻓⼦数组，根据 nums[i] 的值，可以分为三种情况：

nums[i] = 0 时，所有以 i 为结尾的⼦数组的乘积都不可能是负数，此时 g[i] =0 ；
nums[i] < 0 时，那么直接找到 f[i - 1] 的值（这⾥请再读⼀遍 f[i - 1] 代表的意义，并且考虑如果 f[i - 1] 的结值是 0 的话，影不影响结果），然后加⼀即可（因为正数 * 负数 = 负数），此时 g[i] = f[i - 1] + 1 ；
nums[i] > 0 时，此时我们要看 g[i - 1] 的值（这⾥请再读⼀遍 g[i - 1] 代表的意义。因为正数 * 负数 = 负数），根据 g[i - 1] 的值，⼜要分两种情况：

1. g[i - 1] = 0 ，说明以 i - 1 为结尾的乘积为负数的最⻓⼦数组是不存在的，⼜因为 nums[i] > 0 ，所以以 i 结尾的乘积为负数的最⻓⼦数组也是不存在的，此时 f[i] = 0 ；
2. g[i - 1] != 0 ，说明以 i - 1 为结尾的乘积为负数的最⻓⼦数组是存在的，⼜因为 nums[i] > 0 ，所以 i 结尾的乘积为正数的最⻓⼦数组就等于 g[i -1] + 1 ；

综上所述， nums[i] > 0 时， g[i] = g[i - 1] == 0 ? 0 : g[i - 1] +1 ;

这⾥的推导⽐较绕，因为不断的出现「正数和负数」的分情况讨论，我们只需根据下⾯的规则，严格找到此状态下需要的 dp 数组即可：

正数 * 正数 = 正数
负数 * 负数 = 正数
负数 * 正数 = 正数 * 负数 = 负数

3. 初始化：

可以在最前⾯加上⼀个「辅助结点」，帮助我们初始化。使⽤这种技巧要注意两个点：

辅助结点⾥⾯的值要「保证后续填表是正确的」；
「下标的映射关系」。
在本题中，最前⾯加上⼀个格⼦，并且让 f[0] = g[0] = 0 即可。

4. 填表顺序：

根据「状态转移⽅程」易得，填表顺序为「从左往右，两个表⼀起填」。

5. 返回值：

根据「状态表⽰」，我们要返回 f 表中的最⼤值。

代码呈现：

class Solution {
public:
    int getMaxLen(vector<int>& nums) 
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        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;
    }
};

2.5 第五题

题目链接：413. 等差数列划分 - 力扣（LeetCode）

题目描述：

算法思路：

1. 状态表⽰：

由于我们的研究对象是「⼀段连续的区间」，如果我们状态表⽰定义成 [0, i] 区间内⼀共有多少等差数列，那么我们在分析 dp[i] 的状态转移时，会⽆从下⼿，因为我们不清楚前⾯那么多的「等差数列都在什么位置」。所以说，我们定义的状态表⽰必须让等差数列「有迹可循」，让状态转移的时候能找到「⼤部队」。因此，我们可以「固定死等差数列的结尾」，定义下⾯的状态表⽰：

dp[i] 表⽰必须「以 i 位置的元素为结尾」的等差数列有多少种。

2. 状态转移⽅程：

我们需要了解⼀下等差数列的性质：如果 a b c 三个数成等差数列，这时候来了⼀个 d ，其中 b c d 也能构成⼀个等差数列，那么 a b c d 四个数能够成等差序列吗？答案是：显然的。因为他们之间相邻两个元素之间的差值都是⼀样的。有了这个理解，我们就可以转⽽分析我们的状态转移⽅程了。

对于 dp[i] 位置的元素 nums[i] ，会与前⾯的两个元素有下⾯两种情况：

nums[i - 2], nums[i - 1], nums[i] 三个元素不能构成等差数列：那么以nums[i] 为结尾的等差数列就不存在，此时 dp[i] = 0 ；
nums[i - 2], nums[i - 1], nums[i] 三个元素可以构成等差数列：那么以nums[i - 1] 为结尾的所有等差数列后⾯填上⼀个 nums[i] 也是⼀个等差数列，此时dp[i] = dp[i - 1] 。但是，因为 nums[i - 2], nums[i - 1], nums[i] 三者⼜能构成⼀个新的等差数列，因此要在之前的基础上再添上⼀个等差数列，于是dp[i] = dp[i - 1] + 1 。

综上所述：状态转移⽅程为：

当： nums[i - 2] + nums[i] != 2 * nums[i - 1] 时， dp[i] = 0
当： nums[i - 2] + nums[i] == 2 * nums[i - 1] 时， dp[i] = 1 + dp[i - 1]

3. 初始化：

由于需要⽤到前两个位置的元素，但是前两个位置的元素⼜⽆法构成等差数列，因此 dp[0]=dp[1]= 0 。

4. 填表顺序：

毫⽆疑问是「从左往右」。

5. 返回值：

因为我们要的是所有的等差数列的个数，因此需要返回整个 dp 表⾥⾯的元素之和。

代码呈现：

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) 
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        int n = nums.size();
        vector<int> dp(n);
        int sum = 0;
        for (int i = 2; i < n; i++) 
        {
            dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] ? dp[i - 1] + 1 : 0;
            sum += dp[i];
        }
        return sum;
    }
};

2.6 第六题

题目链接：978. 最长湍流子数组 - 力扣（LeetCode）

题目描述：

2.7 第七题

题目链接：978. 最长湍流子数组 - 力扣（LeetCode）

题目描述：

算法思路：

1. 状态表⽰：

f[i] 表⽰：以 i 位置元素为结尾的所有⼦数组中，最后呈现「上升状态」下的最⻓湍流数组的⻓度；
g[i] 表⽰：以 i 位置元素为结尾的所有⼦数组中，最后呈现「下降状态」下的最⻓湍流数组的⻓度。

2. 状态转移⽅程：

对于 i 位置的元素 arr[i] ，有下⾯两种情况：

arr[i] > arr[i - 1] ：如果 i 位置的元素⽐ i - 1 位置的元素⼤，说明接下来应该去找 i -1 位置结尾，并且 i - 1 位置元素⽐前⼀个元素⼩的序列，那就是 g[i- 1] 。更新 f[i] 位置的值： f[i] = g[i - 1] + 1 ；
arr[i] < arr[i - 1] ：如果 i 位置的元素⽐ i - 1 位置的元素⼩，说明接下来应该去找 i - 1 位置结尾，并且 i - 1 位置元素⽐前⼀个元素⼤的序列，那就是f[i - 1] 。更新 g[i] 位置的值： g[i] = f[i- 1] + 1 ；
arr[i] == arr[i - 1] ：不构成湍流数组。

3. 初始化：
所有的元素「单独」都能构成⼀个湍流数组，因此可以将 dp 表内所有元素初始化为 1 。
由于⽤到前⾯的状态，因此我们循环的时候从第⼆个位置开始即可。

4. 填表顺序：

毫⽆疑问是「从左往右，两个表⼀起填」。

5. 返回值：

应该返回「两个 dp 表⾥⾯的最⼤值」，我们可以在填表的时候，顺便更新⼀个最⼤值。

代码呈现：

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) 
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        int n = arr.size();
        vector<int> f(n, 1), g(n, 1);
        int ret = 1;
        for (int i = 1; i < n; i++) 
        {
            if (arr[i - 1] < arr[i])
                f[i] = g[i - 1] + 1;
            else if (arr[i - 1] > arr[i])
                g[i] = f[i - 1] + 1;
            ret = max(ret, max(f[i], g[i]));
        }
        return ret;
    }
};