前言

什么是是动态规划连续子数组、子串系列算法问题?

连续子数组问题通常聚焦于从给定数组中找出满足特定条件的连续片段。例如，最大子数组和问题，目标是在数组中找到一个连续子数组，使其元素之和最大。动态规划通过定义状态来解决这类问题。设dp[i]表示以第i个元素结尾的最大子数组和，状态转移方程为dp[i]=max(nums[i], dp[i - 1]+nums[i])。这意味着要么从当前元素重新开始计算子数组和，要么延续之前的子数组和并加上当前元素。通过这样逐步推导，就能高效找到整个数组中的最大子数组和。​
子串系列算法问题同样常见。比如，最长无重复字符子串问题，要在字符串中找出不包含重复字符的最长连续子串。动态规划通过维护一个状态数组，记录以每个位置字符结尾的最长无重复子串长度。利用哈希表记录字符最近出现的位置，以此来判断当前字符是否在之前的子串中出现过。若未出现或距离足够远，状态转移较为简单；若出现且距离较近，则需要调整子串长度。​
这些连续子数组、子串问题都能通过动态规划将复杂问题分解为一系列可管理的子问题，通过求解子问题并存储结果，避免了大量重复计算，极大地提升了算法效率，从而高效地解决实际场景中诸如数据统计分析、文本处理等领域的相关问题。

下面本文将通过例题带大家更加深入理解动态规划中的子结构问题！

例题

一、最大子数组和

1. 题目链接：最大子数组和
2. 题目描述：

给你⼀个整数数组 nums ，请你找出⼀个具有最大和的连续子数组（⼦数组最少包含⼀个元素），返回其最大和。 子数组 是数组中的⼀个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最⼤，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

3. 解法（动态规划）：
   算法思路： 状态表示： 对于线性 dp ，我们可以用「经验 + 题目要求」来定义状态表示：
   i. 以某个位置为结尾。
   ii. 以某个位置为起点， 这里我们选择比较常用的⽅式，以「某个位置为结尾」，结合「题目要求」，定义⼀个状态表示：
   dp[i] 表示：以 i 位置元素为结尾的「所有⼦数组」中和的最大和。
   状态转移方程：
   dp[i] 的所有可能可以分为以下两种：
   i. ⼦数组的长度为 1 ：此时 dp[i] = nums[i] ；
   ii. ⼦数组的长度大于 1 ：此时 dp[i] 应该等于 以 i - 1 做结尾的「所有子数组」中和的最大值再加上 nums[i] ，也就是 dp[i - 1] + nums[i] 。 由于我们要的是「最大值」，因此应该是两种情况下的最⼤值，因此可得转移方程：
   dp[i] = max(nums[i], dp[i - 1] + nums[i]) 。
   初始化： 可以在最前⾯加上⼀个「辅助结点」，帮助我们初始化。使用这种技巧要注意两个点：
   i. 辅助结点里面的值要「保证后续填表是正确的」；
   ii. 「下标的映射关系」。
   在本题中，最前面加上⼀个格子，并且让 dp[0] = 0 即可。
   填表顺序：
   根据「状态转移方程」易得，填表顺序为「从左往右」。
   返回值： 状态表示为「以 i 为结尾的所有子数组」的最大值，但是最大子数组和的结尾我们是不确定的。 因此我们需要返回整个 dp 表中的最大值。

4. 代码示例：

 public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        int ret = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            dp[i] = Math.max(nums[i - 1], dp[i - 1] + nums[i - 1]);
            ret = Math.max(dp[i], ret);
        }
        return ret;
    }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

二、环形子数组的最大和

1. 题目链接：环形子数组的最大和
2. 题目描述：

给定⼀个长度为 n 的环形整数数组 nums ，返回 nums 的非空子数组的最大可能和 。 环形数组意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下⼀个元素是 nums[(i +1) % n] ， nums[i] 的前⼀个元素是 nums[(i - 1 + n) % n] 。 子数组 最多只能包含固定缓冲区 nums 中的每个元素⼀次。形式上，对于子数组 nums[i], nums[i +1], …, nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
示例 1：
输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3
示例 2：
输入：nums = [5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最⼤和 5 + 5 = 10

3. 解法（动态规划）：
   算法思路： 本题与「最大子数组和」的区别在于，考虑问题的时候不仅要分析「数组内的连续区域」，还要考虑「数组首尾相连」的⼀部分。结果的可能情况分为以下两种：
   i. 结果在数组的内部，包括整个数组；
   ii. 结果在数组首尾相连的⼀部分上。 其中，对于第⼀种情况，我们仅需按照「最大子数组和」的求法就可以得到结果，记为 fmax 。 对于第⼆种情况，我们可以分析⼀下：
   i. 如果数组首尾相连的⼀部分是最大的数组和，那么数组中间就会空出来一部分；
   ii. 因为数组的总和 sum 是不变的，那么中间连续的⼀部分的和⼀定是最小的； 因此，我们就可以得出⼀个结论，对于第二种情况的最大和，应该等于 sum - gmin ，其中gmin 表示数组内的「最小子数组和」。
   两种情况下的最大值，就是我们要的结果。 但是，由于数组内有可能全部都是负数，第⼀种情况下的结果是数组内的最⼤值（是个负数），第 ⼆种情况下的 gmin == sum ，求的得结果就会是 0 。若直接求两者的最⼤值，就会是 0 。但 是实际的结果应该是数组内的最⼤值。对于这种情况，我们需要特殊判断⼀下。 由于「最⼤⼦数组和」的⽅法已经讲过，这⾥只提⼀下「最⼩⼦数组和」的求解过程，其实与「最 ⼤⼦数组和」的求法是⼀致的。⽤ f 表⽰最⼤和， g 表⽰最⼩和。
   状态表⽰：
   g[i] 表⽰：以 i 做结尾的「所有⼦数组」中和的最⼩值。
   状态转移⽅程：
   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]) 。
   初始化： 可以在最前⾯加上⼀个辅助结点，帮助我们初始化。使⽤这种技巧要注意两个点：
   i. 辅助结点⾥⾯的值要保证后续填表是正确的；
   ii. 下标的映射关系。 在本题中，最前面加上⼀个格⼦，并且让 g[0] = 0 即可。
   填表顺序： 根据状态转移⽅程易得，填表顺序为「从左往右」。
   返回值：
   a. 先找到 f 表里面的最⼤值 -> fmax ；
   b. 找到 g 表⾥⾯的最⼩值 -> gmin ；
   c. 统计所有元素的和 -> sum ；
   b. 返回 sum == gmin ? fmax : max(fmax, sum - gmin) 。

4. 代码示例：

   public int maxSubarraySumCircular(int[] nums) {
        int n  =  nums.length;
        int[] f = new int[n+1];
        int[] g = new int[n+1];
        int sum = 0, fmax = Integer.MIN_VALUE, gmin = Integer.MAX_VALUE;
        for(int i = 1;i<=n;i++){
            int x = nums[i-1];
            f[i] = Math.max(x,x+f[i-1]);
            fmax = Math.max(fmax,f[i]);
            g[i]  = Math.min(x,x+g[i-1]);
            gmin = Math.min(gmin,g[i]);
            sum+=x;
        }
        return sum == gmin ? fmax : Math.max(fmax, sum - gmin);
    }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15

三、 乘积最大子数组

1. 题目链接：乘积最大子数组
2. 题目描述：

给你⼀个整数数组 nums ，请你找出数组中乘积最⼤的非空连续子数组（该⼦数组中至少包含⼀个 数字），并返回该⼦数组所对应的乘积。 测试⽤例的答案是⼀个 32-位 整数。 ⼦数组 是数组的连续⼦序列。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释:子数组 [2,3] 有最⼤乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0

3. 解法（动态规划）：
   算法思路：
   这道题与「最⼤⼦数组和」⾮常相似，我们可以效仿着定义⼀下状态表⽰以及状态转移：
   i. dp[i] 表⽰以 i 为结尾的所有⼦数组的最⼤乘积，
   ii. 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 表」。
   状态表示：
   f[i] 表⽰：以 i 结尾的所有⼦数组的最大乘积，
   g[i] 表⽰：以 i 结尾的所有⼦数组的最小乘积。
   状态转移⽅程： 遍历每⼀个位置的时候，我们要同步更新两个 dp 数组的值。 对于 f[i] ，也就是「以 i 为结尾的所有⼦数组的最⼤乘积」，对于所有⼦数组，可以分为下面三种形式：
   i. 子数组的长度为 1 ，也就是 nums[i] ；
   ii. ⼦数组的长度⼤于 1 ，但 nums[i] > 0 ，此时需要的是 i - 1 为结尾的所有子数组 的最大乘积 f[i - 1] ，再乘上 nums[i] ，也就是 nums[i] * f[i - 1] ；
   iii. 子数组的⻓度大于 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 为结尾的所有子数组的最小乘积」，对于所有子数组，可以分为下面三种形式：
   i. ⼦数组的长度为 1 ，也就是 nums[i] ；
   ii. ⼦数组的长度大于 1 ，但 nums[i] > 0 ，此时需要的是 i - 1 为结尾的所有⼦数组 的最小乘积 g[i - 1] ，再乘上 nums[i] ，也就是 nums[i] * g[i - 1] ；
   iii. ⼦数组的⻓度⼤于 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 ，三种情况其实都包含了）
   初始化： 可以在最前面加上⼀个辅助结点，帮助我们初始化。使用这种技巧要注意两个点：
   i. 辅助结点里面的值要保证后续填表是正确的；
   ii. 下标的映射关系。 在本题中，最前⾯加上⼀个格⼦，并且让 f[0] = g[0] = 1 即可。
   填表顺序： 根据状态转移方程易得，填表顺序为「从左往右，两个表⼀起填」。
   返回值： 返回 f 表中的最大值。

4. 代码示例：

 public int maxProduct(int[] nums) {
        int n  = nums.length;
        int[] f = new int[n+1];
        int[] g = new int[n+1];
        int ret = Integer.MIN_VALUE;
        f[0] = g[0] = 1;
        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] = Math.max(x, Math.max(y, z));
            g[i] = Math.min(x, Math.min(y, z));
            ret = Math.max(ret, f[i]);
        }
            return ret; 
    }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14

四、乘积为正数的最长子数组

1. 题目链接：乘积为正数的最长子数组
2. 题目描述：

给你⼀个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
⼀个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。 请你返回乘积为正数的最长子数组长度。
示例 1：
输入：nums = [1,-2,-3,4]
输出：4
解释：数组本身乘积就是正数，值为 24 。
示例 2：
输入：nums = [0,1,-2,-3,-4]
输出：3
解释：最长乘积为正数的⼦数组为 [1,-2,-3] ，乘积为 6 。 注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。
示例 3：
输⼊：nums = [-1,-2,-3,0,1]
输出：2
解释：乘积为正数的最⻓⼦数组是 [-1,-2] 或者 [-2,-3] 。

3. 解法（动态规划）：
   算法思路：
   继续效仿「最大子数组和」中的状态表示，尝试解决这个问题。 状态表示： dp[i] 表示「所有以 i 结尾的子数组，乘积为正数的最长子数组的长度」。
   思考状态转移：对于 i 位置上的 nums[i] ，我们可以分三种情况讨论：
   i. 如果 nums[i] = 0 ，那么所有以 i 为结尾的⼦数组的乘积都不可能是正数，此时dp[i] = 0 ；
   ii. 如果 nums[i] > 0 ，那么直接找到 dp[i - 1] 的值（这里请再读⼀遍 dp[i - 1] 代表的意义，并且考虑如果 dp[i - 1] 的结值是 0 的话，影不影响结果），然后加一即可，此时 dp[i] = dp[i - 1] + 1 ；
   iii. 如果 nums[i] < 0 ，这时候你该蛋疼了，因为在现有的条件下，你根本没办法得到此时 的最长长度。因为乘法是存在「负负得正」的，单单靠⼀个 dp[i - 1] ，我们无法推导 出 dp[i] 的值。
   但是，如果我们知道「以 i - 1 为结尾的所有子数组，乘积为负数的最长子数组的长度」g[i - 1] ，那么此时的 dp[i] 是不是就等于 g[i - 1] + 1 呢？
   通过上⾯的分析，我们可以得出，需要两个 dp 表，才能推导出最终的结果。不仅需要⼀个「乘积 为正数的最⻓⼦数组」，还需要⼀个「乘积为负数的最长子数组」。
   状态表示：
   f[i] 表示：以 i 结尾的所有⼦数组中，乘积为「正数」的最长子数组的⻓度；
   g[i] 表示：以 i 结尾的所有⼦数组中，乘积为「负数」的最长子数组的⻓度。
   状态转移方程： 遍历每⼀个位置的时候，我们要同步更新两个 dp 数组的值。 对于 f[i] ，也就是以 i 为结尾的乘积为「正数」的最长子数组，根据 nums[i] 的值，可以 分为三种情况：
   i. nums[i] = 0 时，所有以 i 为结尾的子数组的乘积都不可能是正数，此时 f[i] = 0 ；
   ii. nums[i] > 0 时，那么直接找到 f[i - 1] 的值（这里请再读⼀遍 f[i - 1] 代表 的意义，并且考虑如果 f[i - 1] 的结值是 0 的话，影不影响结果），然后加一即可， 此时 f[i] = f[i - 1] + 1 ；
   iii. nums[i] < 0 时，此时我们要看 g[i - 1] 的值（这里请再读⼀遍 g[i - 1] 代 表的意义。因为负负得正，如果我们知道以 i - 1 为结尾的乘积为负数的最长子数组的长度，加上 1 即可），根据 g[i - 1] 的值，又要分两种情况：
   g[i - 1] = 0 ，说明以 i - 1 为结尾的乘积为负数的最长子数组是不存在的，又因为 nums[i] < 0 ，所以以 i 结尾的乘积为正数的最⻓⼦数组也是不存在的，此 时 f[i] = 0 ；
   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] 的值，可以分为三种情况：
   i. nums[i] = 0 时，所有以 i 为结尾的子数组的乘积都不可能是负数，此时 g[i] = 0 ；
   ii. nums[i] < 0 时，那么直接找到 f[i - 1] 的值（这里请再读⼀遍 f[i - 1] 代表 的意义，并且考虑如果 f[i - 1] 的结值是 0 的话，影不影响结果），然后加⼀即可 （因为正数 * 负数 = 负数），此时 g[i] = f[i - 1] + 1 ；
   iii. nums[i] > 0 时，此时我们要看 g[i - 1] 的值（这里请再读⼀遍 g[i - 1] 代 表的意义。因为正数 * 负数 = 负数），根据 g[i - 1] 的值，又要分两种情况：
   g[i - 1] = 0 ，说明以 i - 1 为结尾的乘积为负数的最⻓⼦数组是不存在的，又因为 nums[i] > 0 ，所以以 i 结尾的乘积为负数的最⻓⼦数组也是不存在的，此 时 f[i] = 0 ；
   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 数组即可：
   i. 正数 * 正数 = 正数
   ii. 负数 * 负数 = 正数
   iii. 负数 * 正数 = 正数 * 负数 = 负数
   初始化： 可以在最前⾯加上⼀个「辅助结点」，帮助我们初始化。使⽤这种技巧要注意两个点：
   i. 辅助结点里面的值要「保证后续填表是正确的」；
   ii. 「下标的映射关系」。
   在本题中，最前面加上⼀个格子，并且让 f[0] = g[0] = 0 即可。
   填表顺序： 根据「状态转移⽅程」易得，填表顺序为「从左往右，两个表⼀起填」。
   返回值： 根据「状态表示」，我们要返回 f 表中的最⼤值。

4. 代码示例：

  public int getMaxLen(int[] nums) {
        int n = nums.length;
        int[] f  =new int[n+1];
        int[] g = new int[n+1];
        int ret = Integer.MIN_VALUE;
        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 = Math.max(ret,f[i]);
        }
        return ret；
    }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17

五、等差数列划分

1. 题目链接：等差数列划分
2. 题目描述：

如果⼀个数列 ⾄少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。 • 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。 给你⼀个整数数组 nums ，返回数组 nums 中所有为等差数组的子数组个数。子数组 是数组中的⼀个连续序列。
示例 1：
输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个⼦等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] ⾃⾝。
示例 2：
输入：nums = [1]
输出：0

3. 解法（动态规划）： 算法思路：
   状态表⽰： 由于我们的研究对象是「⼀段连续的区间」，如果我们状态表⽰定义成 [0, i] 区间内⼀共有多 少等差数列，那么我们在分析 dp[i] 的状态转移时，会无从下手，因为我们不清楚前面那么多 的「等差数列都在什么位置」。所以说，我们定义的状态表⽰必须让等差数列「有迹可循」，让状 态转移的时候能找到「大部队」。因此，我们可以「固定死等差数列的结尾」，定义下面的状态表示：
   dp[i] 表示必须「以 i 位置的元素为结尾」的等差数列有多少种。
   状态转移方程： 我们需要了解⼀下等差数列的性质：如果 a b c 三个数成等差数列，这时候来了⼀个 d ，其 中 b c d 也能构成⼀个等差数列，那么 a b c d 四个数能够成等差序列吗？答案是：显然 的。因为他们之间相邻两个元素之间的差值都是⼀样的。有了这个理解，我们就可以转而分析我们的状态转移方程了。 对于 dp[i] 位置的元素 nums[i] ，会与前面的两个元素有下面两种情况：
   i. nums[i - 2], nums[i - 1], nums[i] 三个元素不能构成等差数列：那么以nums[i] 为结尾的等差数列就不存在，此时 dp[i] = 0 ；
   ii. 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]
   初始化： 由于需要用到前两个位置的元素，但是前两个位置的元素又无法构成等差数列，因此 dp[0] = dp[1] = 0 。
   填表顺序： 毫无疑问是「从左往右」。
   返回值： 因为我们要的是所有的等差数列的个数，因此需要返回整个 dp 表里面的元素之和。

4. 代码示例：

 public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if(n<2) return 0;
        int[] dp  = new int[n];
        dp[0] = 0;
        dp[1] = 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;
            }
        }
       int sum = 0;
       for(int x :dp){
        sum+=x;
       }
       return sum;
    }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19

六、最长湍流子数组

1. 题目链接：最长湍流子数组
2. 题目描述：

给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。 如果比较符号在子数组中的每个相邻元素对之间翻转，则该⼦数组是湍流子数组 。 更正式地来说，当 arr 的子数组 A[i], A[i+1], …, A[j] 满足仅满足下列条件时，我们称其为湍流子数 组：若 i <= k < j ：当 k 为奇数时， A[k] > A[k+1]，且 当 k 为偶数时，A[k] < A[k+1]； 或 若 i <= k < j ：当 k 为偶数时，A[k] > A[k+1] ，且当k 为奇数时， A[k] < A[k+1]。
示例 1：
输入：arr = [9,4,2,10,7,8,8,1,9]
输出：5
解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
示例 2：
输入：arr = [4,8,12,16]
输出：2
示例 3：
输入：arr = [100]
输出：1
提示： 1 <= arr.length <= 4 * 10^4
0 <= arr[i] <= 10^9

3. 解法（动态规划）：
   算法思路：
   状态表⽰： 我们先尝试定义状态表⽰为：
   dp[i] 表⽰「以 i 位置为结尾的最⻓湍流数组的⻓度」。
   但是，问题来了，如果状态表⽰这样定义的话，以 i 位置为结尾的最⻓湍流数组的⻓度我们没法从之前的状态推导出来。因为我们不知道前⼀个最长湍流数组的结尾处是递增的，还是递减的。因此，我们需要状态表⽰能表示多⼀点的信息：要能让我们知道这⼀个最长湍流数组的结尾是「递 增」的还是「递减」的。 因此需要两个dp 表：
   f[i] 表示：以 i 位置元素为结尾的所有子数组中，最后呈现「上升状态」下的最长湍流数组的长度；
   g[i] 表示：以 i 位置元素为结尾的所有子数组中，最后呈现「下降状态」下的最长湍流数组的长度。
   状态转移方程： 对于 i 位置的元素 arr[i] ，有下⾯面种情况：
   i. arr[i] > arr[i - 1] ：如果 i 位置的元素比i - 1 位置的元素大，说明接下来 应该去找 i -1 位置结尾，并且 i - 1 位置元素⽐前⼀个元素⼩的序列，那就是 g[i

• 1] 。更新 f[i] 位置的值： f[i] = g[i - 1] + 1 ；
  ii. arr[i] < arr[i - 1] ：如果 i 位置的元素比 i - 1 位置的元素小，说明接下来 应该去找 i - 1 位置结尾，并且 i - 1 位置元素比前⼀个元素大的序列，那就是f[i - 1] 。更新 g[i] 位置的值： g[i] = f[i - 1] + 1 ；
  iii. arr[i] == arr[i - 1] ：不构成湍流数组。
  初始化： 所有的元素「单独」都能构成⼀个湍流数组，因此可以将 dp 表内所有元素初始化为 1 。 由于用到前面的状态，因此我们循环的时候从第⼆个位置开始即可。
  填表顺序： 毫无疑问是「从左往右，两个表⼀起填」。
  返回值： 应该返回「两个 dp 表里面的最大值」，我们可以在填表的时候，顺便更新⼀个最大值。

4. 代码示例：

  public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        int[] f  = new int[n];
        int[] g = new int[n];
        f[0] = 1;g[0] = 1;
        int ret = 1;
        for(int i = 0;i<n;i++){
            f[i] = 1;
            g[i] = 1;
        }
        for(int i = 1;i<n;i++){
            if(arr[i]>arr[i-1]){
                f[i] = g[i-1]+1;
            }else if(arr[i]<arr[i-1]){
                g[i] = f[i-1] + 1;
            }
            ret = Math.max(ret,Math.max(f[i],g[i]));
        }
        return ret;
    }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20

七、单词拆分

1. 题目链接：单词拆分
2. 题目描述：

给你⼀个字符串 s 和⼀个字符串列表 wordDict 作为字典。请你判断是否可以利⽤字典中出现的单词
拼接出 s 。 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释:返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。
示例 2：
输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释:返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。 注意，你可以重复使用字典中的单词。
示例 3：
输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

3. 解法（动态规划）：
   算法思路：
   状态表示： 对于线性 dp ，我们可以⽤「经验 + 题目要求」来定义状态表示：
   i. 以某个位置为结尾
   ii. 以某个位置为起点，这里我们选择比较常用的方式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表示：dp[i] 表示： [0, i] 区间内的字符串，能否被字典中的单词拼接而成。
   状态转移⽅程： 对于 dp[i] ，为了确定当前的字符串能否由字典里面的单词构成，根据最后⼀个单词的起始位 置 j ，我们可以将其分解为前后两部分：
   i. 前面⼀部分 [0, j - 1] 区间的字符串；
   ii. 后面⼀部分 [j, i] 区间的字符串。 其中前面部分我们可以在 dp[j - 1] 中找到答案，后⾯部分的子串可以在字典里面找到。 因此，我们得出⼀个结论：当我们在从 0 ~ i 枚举 j 的时候，只要 dp[j - 1] = true并且后面部分的⼦串 s.substr(j, i - j + 1) 能够在字典中找到，那么 dp[i] = true 。
   初始化： 可以在最前面加上⼀个「辅助结点」，帮助我们初始化。使用这种技巧要注意两个点：
   i. 辅助结点里面的值要「保证后续填表是正确的」；
   ii. 「下标的映射关系」。
   在本题中，最前面加上⼀个格⼦，并且让 dp[0] = true ，可以理解为空串能够拼接而成。 其中为了⽅便处理下标的映射关系，我们可以将字符串前⾯加上⼀个占位符 s = ’ ’ + s ，这 样就没有下标的映射关系的问题了，同时还能处理「空串」的情况。
   填表顺序： 显而易见，填表顺序「从左往右」。
   返回值：由「状态表⽰」可得：返回 dp[n] 位置的布尔值

4. 代码示例：

 public boolean wordBreak(String s, List<String> wordDict) {
       Set<String> hash  =new HashSet(wordDict);
       int n = s.length();
       boolean[] dp = new boolean[n+1];
       dp[0] =true;
       s = " "+ s;
       for(int i = 1;i<=n;i++){
        for(int j = i;j>=1;j--){
            if(dp[j-1]&&hash.contains(s.substring(j , i+1))){
                dp[i] = true;
                break;
            }
        }
       }
       return dp[n];
    }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16

八、环绕字符串中唯一的子字符串

1. 题目链接：环绕字符串中唯一的子字符串
2. 题目描述：

定义字符串 base 为⼀个 “abcdefghijklmnopqrstuvwxyz” 无限环绕的字符串，所以 base 看起来是 这样的：“…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…”. 给你⼀个字符串 s ，请你统计并返回 s 中有多少 不同⾮空⼦串 也在 base 中出现。
示例 1：
输入：s = “a”
输出：1
解释：字符串 s 的⼦字符串 “a” 在 base 中出现。
示例 2：
输入：s = “cac”
输出：2 解释：字符串 s 有两个⼦字符串 (“a”, “c”) 在 base 中出现。
示例 3：
输入：s = “zab”
输出：6 解释：字符串 s 有六个⼦字符串 (“z”, “a”, “b”, “za”, “ab”, and “zab”) 在 base 中出现。
提示：1 <= s.length <= 105
s 由小写英文字母组成

3. 解法（动态规划）：
   算法思路：
   状态表示： 对于线性 dp ，我们可以⽤「经验 + 题目要求」来定义状态表示：
   i. 以某个位置为结尾
   ii. 以某个位置为起点，这里我们选择比较常用的方式，以某个位置为结尾，结合题目要求，定义⼀个状态表示：
   dp[i] 表示：以 i 位置的元素为结尾的所有⼦串里面，有多少个在 base 中出现过。
   状态转移方程： 对于 dp[i] ，我们可以根据⼦串的「⻓度」划分为两类：
   i. 子串的长度等于 1 ：此时这⼀个字符会出现在 base 中；
   ii. 子串的长度大于 1 ：如果 i 位置的字符和 i - 1 位置上的字符组合后，出现在 base中的话，那么 dp[i - 1] 里面的所有子串后面填上⼀个 s[i] 依旧在 base 中出 现。因此 dp[i] = dp[i - 1] 。 综上， dp[i] = 1 + dp[i - 1] ，其中 dp[i - 1] 是否加上需要先做⼀下判断。
   初始化： 可以根据「实际情况」，将表⾥⾯的值都初始化为 1 。
   填表顺序： 显⽽易⻅，填表顺序「从左往右」。
   返回值：
   这里不能直接返回 dp 表里面的和，因为会有重复的结果。在返回之前，我们需要先「去重」：
   i. 相同字符结尾的 dp 值，我们仅需保留「最⼤」的即可，其余 dp 值对应的⼦串都可以在 最大的里面找到；
   ii. 可以创建⼀个大小为 26 的数组，统计所有字符结尾的最大dp 值。 最后返回「数组中所有元素的和」即可。

4. 代码示例：

  public int findSubstringInWraproundString(String ss) {
        int n = ss.length();
        char[] s = ss.toCharArray();
        // 1. 利⽤ dp 得到每⼀个位置为结尾的最⻓连续数组的⻓度
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) dp[i] = 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];
        // 2. 去重
        int[] hash = new int[26];
        for (int i = 0; i < n; i++)
            hash[s[i] - 'a'] = Math.max(hash[s[i] - 'a'], dp[i]);

        // 3. 返回结果
        int sum = 0;
        for (int x : hash) sum += x;
        return sum;
    }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19

结语

本文到这里就结束了，主要通过几道动态规划（连续子结构）的题目，带大家深入了解了这类算法题目的处理方式以及如何建立状态转移方程。

以上就是本文全部内容，感谢各位能够看到最后，如有问题，欢迎各位大佬在评论区指正，希望大家可以有所收获！创作不易，希望大家多多支持！

最后，大家再见！祝好！我们下期见！