【动态规划】子数组系列（下）

子数组问题

文章目录

• 【动态规划】子数组系列（下）
• • 1. 等差数组划分
  • • 1.1 题目解析
    • 1.2 算法原理
    • • 1.2.1 状态表示
      • 1.2.2 状态转移方程
      • 1.2.3 初始化
      • 1.2.4 填表顺序
      • 1.2.5 返回值
    • 1.3 代码实现
  • 2. 最长湍流子数组
  • • 2.1 题目解析
    • 2.2 算法原理
    • • 2.2.1 状态表示
      • 2.2.2 状态转移方程
      • 2.2.3 初始化
      • 2.2.4 填表顺序
      • 2.2.5 返回值
    • 2.3 代码实现
  • 3. 单词划分
  • • 3.1 题目解析
    • 3.2 算法原理
    • • 3.2.1 状态表示
      • 3.2.2 状态转移方程
      • 3.2.3 初始化
      • 3.2.4 填表顺序
      • 3.2.5 返回值
    • 3.3 代码实现
  • 4. 环绕字符串中唯一的子字符串
  • • 4.1 题目解析
    • 4.2 算法原理
    • • 4.2.1 状态表示
      • 4.2.2 状态转移方程
      • 4.2.3 初始化
      • 4.2.4 填表顺序
      • 4.2.5 返回值
    • 4.3 代码实现

【动态规划】子数组系列（下）

1. 等差数组划分

传送门：力扣413

题目：

1.1 题目解析

1.2 算法原理

1.2.1 状态表示

根据经验+题目要求：

1. 题目给了一个一维数组，要求得到“等差数列”个数
   • 一维dp表，大小为n
2. 以…为结尾，去研究
   • 子数组问题常见就是“以…为结尾的子数组”集合

故得到状态表示：

dp[i]表示以i为结尾的子数组中，等差数组的个数~

1.2.2 状态转移方程

等差数组的特性：公差一致

• a、b、c为等差数列，b、c、d为等差数列，那么a、b、c、d也为等差数列！

对于[i]这个位置：

如果b + dp[i] == 2 * c，那么nums[i]为结尾的子数组至少有b、c、dp[i]这一个等差数列

• 如果c为结尾的子数组有等差数列，那么a、b、c、nums[i]等等…数列都是等差数列，即c为结尾的子数组中的等差数列继承给nums[i]

如果b + dp[i] != 2 * c，那么nums[i]为结尾的子数组一个等差数列都没有~

故得到状态转移方程：

dp[i] = nums[i - 2] + nums[i] == nums[i - 1] * 2 ? 1 + dp[i - 1] : 0;

1.2.3 初始化

这里用到dp[i - 1]所以需要处理dp[0]，而实际上dp[0]和dp[1]是绝对为0的，因为等差数列至少要3个元素

所以不必理会~

1.2.4 填表顺序

从左往右依次填（从2开始）

1.2.5 返回值

本题不是以dp表的某个值为返回值，而是dp表值的总和，dp表每个元素是符合要的子数组数，而返回值即是符合要求的子数组的总和~

1.3 代码实现

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        //1. 创建dp表
        //2. 初始化
        //3. 填表顺序
        //4. 返回值
        int n = nums.length;
        int[] dp = new int[n];
        int sum = 0;
        for(int i = 2; i < n; i++) {
            dp[i] = nums[i - 2] + nums[i] == 2 * nums[i - 1] ? 1 + dp[i - 1] : 0;
            sum += dp[i];
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2. 最长湍流子数组

传送门：力扣978

题目：

2.1 题目解析

2.2 算法原理

2.2.1 状态表示

“经验+题目要求”快速得到一维dp表，dp[i]代表以i为结尾的子数组中，是湍流子数组的最长长度

而这样的状态，不太细，至少我们刚才划分出了两种情况，那么我联系等一下的状态转移方程，我们不知道dp[i - 1]是下面的几种情况：

对于相等的情况，dp值必为1，因为相等为结尾的子数组，必然不为湍流子数组

有f[i]表示，以i为结尾的子数组，末尾为上升的湍流子数组的最长长度

g[i]表示，以i为结尾的子数组，末尾为下降的湍流子数组的最长长度

疑问：可以代码判断其前面是哪种情况啊~

没错，但是我们每次都要选择其中的较大值，那么另一种情况就被我们放弃了，而这是不一定的，“另一个情况”可能是“更长湍流子数组的起源”

2.2.2 状态转移方程

结合刚才的分析有，以i为结尾的子数组最后一段为上升还是下降的判断：

如果arr[i - 1] < arr[i]，即上升

• f[i] = g[i - 1] + 1
• g[i] = 1

对于f表，找到i - 1 下降子数组的最长长度，然后续上去

如果arr[i - 1] < arr[i]，即下降

• f[i] = 1
• g[i] = f[i - 1] + 1

对于g表，找到i - 1 上升子数组的最长长度，然后续上去

如果arr[i - 1] == arr[i]，即相等

• f[i] = 1
• g[i] = 1
  

2.2.3 初始化

dp[i]都大于等于1，dp[0]显然是1~

初始化f表g表每个元素为1

2.2.4 填表顺序

从左往右依次填

2.2.5 返回值

dp表中的最大值

2.3 代码实现

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        //1. 创建dp表
        //2. 初始化
        //3. 填表
        //4. 返回值
        int n = arr.length;
        int max = 1;
        int[] f = new int[n];
        int[] g = new int[n];
        Arrays.fill(f, 1);
        Arrays.fill(g, 1);
        for(int i = 1; i < n; i++) {
            if(arr[i] > arr[i - 1]) {
                f[i] += g[i - 1];
            }else if(arr[i] < arr[i - 1]) {
                g[i] += f[i - 1];
            }   
            max = Math.max(max, Math.max(f[i], g[i]));
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3. 单词划分

传送门：力扣139

题目：

3.1 题目解析

3.2 算法原理

3.2.1 状态表示

“经验+题目要求”可迅速得到，一维dp表（大小为n）

dp[i] 表示 [0, i]这段字符串，是否可以有字典的单词拼接成

3.2.2 状态转移方程

增加第i这个字符后能被成功拼接就要有下面这个判断：

而我们只需要从右往左去判断紫色部分能否构成一个单词并且蓝色部分可以被拼接即可，因为找到两个单词，也在蓝色部分的之前判断里判断过了，所以没有必要~

即找到一个j

• 使得[0, j - 1]可以被单词拼接 => dp[j - 1]
• 使得[j, i]是一个单词 => contains(substring(j, i + 1))（伪代码）

得到状态转移方程：

if(set.contains(s.substring(0, i + 1))) {
    dp[i] = true;
}else {
    for(int j = i; j > 0; j--) {
        if(dp[j - 1] && set.contains(s.substring(j, i + 1))) {
            dp[i] = true;
            break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10

3.2.3 初始化

并没有什么越界问题，java布尔数组默认值为false

• 可以通过一个假数据，去简化代码，但是要考虑下标对应啥的，太麻烦了~

3.2.4 填表顺序

从左往右填表

3.2.5 返回值

返回最后一个元素的值

3.3 代码实现

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //1. 创建dp表
        //2. 初始化
        //3. 填表
        //4. 返回值
        char[] string = s.toCharArray();
        int n = string.length;
        boolean[] dp = new boolean[n];
        Set<String> set = new HashSet(wordDict);
        for(int i = 0; i < n; i++) {
            if(set.contains(s.substring(0, i + 1))) {
                dp[i] = true;
            }else {
                for(int j = i; j > 0; j--) {
                    if(dp[j - 1] && set.contains(s.substring(j, i + 1))) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        return dp[n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

时间复杂度为O（N²）

空间复杂度为O（N + M）

• M为单词数

4. 环绕字符串中唯一的子字符串

传送门：力扣467

题目：

4.1 题目解析

• 并且，满足要求的子串不能重复~

4.2 算法原理

4.2.1 状态表示

由“经验 + 题目要求”可以迅速得到一维dp表（大小为n）

dp[i]表示以i为结尾的子串中，属于base中的子串个数

4.2.2 状态转移方程

分为两种情况：

1. 子串大小为1，dp[i] = 1（一个字母必然出现）
2. 子串大小大于1
   1. string[i]这个字母能续上去，那么就继承dp[i - 1]
   2. 不能续上，就为0

故得到状态转移方程：

dp[i] = 1 + string[i] == string[i - 1] + 1 || (string[i] == ‘a’ && string[i - 1] == ‘z’) ? dp[i - 1] : 0;

4.2.3 初始化

初始化dp表每个值为1，方便计算，并且dp表的元素最小值就为1

4.2.4 填表顺序

从左往右填表

4.2.5 返回值

这里直接返回dp表总和？

• 很显然是不对的！

因为这里可能会出现大量的重复子串！

如何去重？

• 不难想到，重复的子串的特点就是，以同一个字母为结尾
  

返回26个字母对应的dp值之和

4.3 代码实现

class Solution {
    public int findSubstringInWraproundString(String s) {
        //1. 创建dp表
        //2. 初始化
        //3. 填表
        //4. 返回值
        int n = s.length();
        char[] string = s.toCharArray();
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for(int i = 1; i < n; i++) {
            dp[i] += string[i] == string[i - 1] + 1 || 
                (string[i] == 'a' && string[i - 1] == 'z') ? dp[i - 1] : 0;
        }
        int[] count = new int[26];
        for(int i = 0; i < n; i++) {
            int index = string[i] - 'a';
            count[index] = Math.max(count[index], dp[i]);
        }
        int sum = 0;
        for(int i = 0; i < 26; i++) {
            sum += count[i];
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

---

文章到此结束！谢谢观看
可以叫我 小马，我可能写的不好或者有错误，但是一起加油鸭

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/837033