【动态规划】子数组系列

简介: 本文介绍了多个动态规划问题及其解决方案,包括最大子数组和、环形子数组的最大和、乘积最大子数组、乘积为正数的最长子数组长度、等差数列划分、最长湍流子数组、单词拆分及环绕字符串中唯一的子字符串。通过详细的状态定义、转移方程和代码实现,帮助读者理解每类问题的核心思路与解题技巧。

1. 最大子数组和

53. 最大子数组和

状态表示:以 i 位置为结尾时的所有子数组中的最大和

状态转移方程:

i 位置为结尾的子数组又可以分为长度为 1 的和大于 1 的,长度为 1 就是 nums[i] ,长度不为 1 就是 dp[i - 1] + nums[i],最后取这两个的最大值即可

初始化:可以多开一个元素,为了不影响后续的值默认为 0 即可,也可以单独对 dp[0] 进行初始化,就不用多开一个元素了

填表顺序:从左到右

返回值:整个 dp 表中的最大值,因为结果可能是以任意位置结尾的,如果多开一个元素的话最后取最大值就不能再带上这个值了

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        //dp[0] = Math.max(0,nums[0]);
        int res = -0x3f3f3f;
        for(int i = 1;i <= n;i++){
            dp[i] = Math.max(nums[i - 1],dp[i - 1] + nums[i - 1]); 
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

2. 环形子数组的最大和

918. 环形子数组的最大和

这道题和上道题不同的就是是一个环形结构,首尾可以相连,这就会有下面两种情况

情况一和上一题是一样的,就是正常的求最大的子序列和,情况二就是首尾相连的情况,可以转化为求中间部分最小的子序列和,再用总的数组和减去这部分最小的子序列和就是最大子序列和,这两种情况求最大值就可以了

状态表示和状态转移方程都和上一题是类似的

初始化:求最大子序列和时还是 dp[0] 初始化为 0,不过求最小子序列就不一样了

dp[i] = Math.min(nums[i - 1],dp[i - 1] + nums[i - 1]);

求 dp[1] 时需要让最后的结果等于 num[0],所以 dp[i - 1] 就需要设为 0 或者一个很大的数,不过不能设为 int 的最大值,不然可能会溢出

返回值:返回两种情况的最大值,不过有一种情况需要注意,当数组中全是负数的话,第一种情况求的就是负数,第二种情况求的最小值就是整个数组和,再用数组和减去这个最小值就是 0 ,代表什么都不选,肯定是比第一种情况大的,这个时候还是需要返回第一种情况的值

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        int ret1 = Integer.MIN_VALUE;
        int sum = 0;
        for(int i = 1;i <= n;i++){
            dp[i] = Math.max(nums[i - 1],dp[i - 1] + nums[i - 1]);
            ret1 = Math.max(ret1,dp[i]);
            sum += nums[i - 1];
        }
        int ret2 = Integer.MAX_VALUE;
        dp[0] = 0x3f3f3f;
        for(int i = 1;i <= n;i++){
            dp[i] = Math.min(nums[i - 1],dp[i - 1] + nums[i - 1]);
            ret2 = Math.min(ret2,dp[i]);
        }
        if(sum == ret2) return ret1;
        return Math.max(ret1,sum - ret2);
    }
}

3. 乘积最大子数组

152. 乘积最大子数组

这道题求的是乘积最大的子数组,由于是乘法,就意味着两个负数乘完之后也会变成整数

状态表示:先定义为以 i 位置为结尾时的所有子数组中的最大乘积发现,如果是负数的话也可以乘进来,所以可以定义两个状态

以 i 位置为结尾时的所有子数组中的最大乘积

以 i 位置为结尾时的所有子数组中的最小乘积

状态转移方程:

求 f[i] 时,如果说当前元素是一个负数,那么就需要乘上一个最小的负数,也就是 g[i - 1],如果是正数的话正常求前一个状态的最大值再乘当前元素就行,最终确定最大值时需要再加上当前元素,这三个数一起求一个最大值即可

同理,求最小值 g[i] 时,如果说当前元素是一个正数,那么就需要乘上一个最小的负数,也就是 g[i - 1],如果是负数的话就需要找一个最大的正数来乘,最终确定最小值时需要再加上当前元素,这三个数一起求一个最小值即可

初始化:把 f[0] 和 g[0] 设置为 1 就不影响后续的乘积赋值

填表顺序:从左到右

返回值:f 表中的最大值

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        f[0] = 1;
        g[0] = 1;
        int ret = Integer.MIN_VALUE;
        for(int i = 1;i <= n;i++ ){
            f[i] = Math.max(Math.max(nums[i - 1], f[i - 1] * nums[i - 1]), g[i - 1] * nums[i - 1]);
            g[i] = Math.min(Math.min(nums[i - 1], f[i - 1] * nums[i - 1]), g[i - 1] * nums[i - 1]);
            ret = Math.max(ret,f[i]);
        }
        return ret;
    }
}

4. 乘积为正数的最长子数组长度

1567. 乘积为正数的最长子数组长度

状态表示:

f[i]:以 i 位置为结尾的所有子数组中乘积为正数的最长长度

g[i]:以 i 位置为结尾的所有子数组中乘积为负数的最长长度

状态转移方程:

还是和之前一样,可以分为长度为 1 的和长度大于 1 的,当长度为 1 时又可以分为 nums[i] 是正数还是负数两种情况,当是正数时长度就是 1,负数时就是 0,再看长度大于 1 的,也可以分为 nums[i] 是正数还是负数两种情况,当 num[i] 是正数时,就是从以 i - 1 为结尾时数组中的乘积为正数的最长长度加 1 即可,也就是 f[i - 1] + 1,当 num[i] 是负数时,就需要在 i - 1 为结尾时数组中的乘积为负数的长度加上 1,所以需要再定义一个 g[i] 状态数组来表示,也就是 g[i  - 1]  + 1,但是如果之前找不到一个以 i  - 1 为结尾的数组,那么 g[i - 1] 就是 0,此时就不能继续加 1,因为 num[i] 是负数,这个长度不能加

为了简便,长度为 1 时的状态可以和下面长度大于 1 的合并一下,不影响结果

接下来看 g[i] 的状态转移方程:同理,也可以分为长度为 1 和长度大于 1 两种情况,接着二者又可以分为 num[i] 大于 0 和小于 0 两种情况,当 num[i] 大于 0 时,需要找到 i - 1 为结尾的乘积为负数的最长长度,也就是 g[i - 1],然后加 1,这里还是一样的,如果没有找到,那么 g[i - 1] 就是 0,num[i] 为正数,要求的是负数,所以这个 1 需要判断一下才能加,num[i] 小于 0 时,就需要找一个 i - 1 为结尾的乘积为正数的最长长度,也就是 f[i - 1] 再加 1,这时就不需要判断,找不到也没关系,可以直接 + 1

长度为 1 时也可以合并一下,不影响结果

nums[i] 等于 0 的情况直接不考虑就行

初始化:如果 nums[0] 是大于 0 的话,g[1] 应该是 0,也就是 g[0] = 0即可, 如果是小于 0 的话 g[1] 应该是 1,也就是 f[0] 应该是 0

填表顺序:从左到右,两个表一起填

返回值:f 表中的最大值

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

5. 等差数列划分

413. 等差数列划分

状态表示:以 i 位置为结尾时的等差数列的个数

状态转移方程:由于至少需要三个元素才符合题目中等差数列的要求,所以需要判断 i - 2,i - 1,i 三个元素,当这三个元素符合等差数列时,那么以 i - 1 为结尾的等差数列再加上 i 也是等差数列,等差数列的个数就 + 1,如果说这三个元素不符合等差数列,那么以 i 为结尾的等差数列个数就是 0

初始化:由于三个元素才能进行等差数列的判断,所以 dp[0],dp[1] 初始化为 0

返回值:如果数组长度小于 3 直接返回 0,大于等于 3 就返回 dp 数组的和

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int ret = 0;
        if(n < 3) return 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; 
            ret += dp[i];
        }
        return ret;
    }
}

6. 最长湍流子数组

978. 最长湍流子数组

状态表示:先用 dp[i] 来表示以第 i 个位置为结尾时的最长湍流数组的长度

f[i]:表示以第 i 个位置为结尾时表示上升状态的最长湍流数组的长度

f[i]:表示以第 i 个位置为结尾时表示下降状态的最长湍流数组的长度

状态转移方程:

第 i - 1 和 i 位置的状态可能会有下降,上升,相等三种状态,所以定义一个  dp 状态就不够了,需要定义一个上升状态和一个下降状态,当 i - 1 到 i 处于下降状态时,之前应该是处于上升状态的,也就是 f[i - 1],再加上 1 就是以第 i 个位置为结尾时处于下降状态的最长数组长度,上升也是一样的道理,需要在第 i - 1 位置处于下降状态,就是 g[i - 1] + 1,相等时等于 1 即可

初始化:由于 1 个元素也可以称为湍急子数组,所以可以把 0 下标初始化为 1,又因为状态转移方程中的其他情况是 1 ,为了方便,可以把初始的两个 dp 表都初始化为 1

填表顺序:从左到右

返回值:下降和上升状态的最大值

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

7. 单词拆分

139. 单词拆分

状态表示:dp[i] 表示以 i 为结尾时,区间 [0 , i] 之间内能否被字典中的单词拼接而成

状态转移方程:

可以把区间分为两段,设 j 为最后一个单词的起始位置的下标,如果 [0 , j - 1] 区间内能够被字典中的单词拼接而成,也就是 dp[j - 1],再加上 j ~ i 区间的单词在数组中,那么就说明 0 ~ i 区间可以被字典中的单词拼接而成

初始化:为了方便表示 ,dp 数组还是开 n + 1(n 为所给字符串的长度),此时 dp[0] 需要设置为 true 才能不影响后续的判断,如果是 false 的话,那么后面区间就一直都不可以被拼接,dp 数组长度 + 1 之后,为了更方便的表示下标的映射关系,可以把原来的字符串 s 最前面加一个长度为 1 的占位符,这样字符串的下标也对应着 dp 表的下标

填表顺序:从左到右

返回值:dp[n]

为了便于查找 j ~ i 的字符串是否在字典中,可以把题中的字典映射到哈希表中

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        s = " " + s;
        Set<String> hash = new HashSet(wordDict);
        for(int i = 1;i <= n;i++){
            //字符串长度 + 1,对应的 j 最小就是 1 下标
            for(int j = i;j >= 1;j--){
                //substring 前闭后开 ,所以 i + 1
                if(dp[j - 1] && hash.contains(s.substring(j,i + 1))){
                    dp[i] = true;
                    //如果找到一种再往前就不用找了
                    break;
                }
            }   
        }
        return dp[n];
    }
}

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

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

状态表示:dp[i] 表示以 i 位置为结尾时,有多少子串出现

状态转移方程:

和上一题其实差不多,可以分为长度为 1 和长度大于 1 的,只需要判断是否是连续的,前一个是“z”后一个是 "a" 也算是连续的

初始化:由于长度为 1 时可以算出现一次,长度大于 1 就是找到以 i - 1 为结尾的子串再加上 s[i] ,整体的数量还是 dp[i - 1],dp[i] 就是把长度为 1 和长度大于 1 的两种情况加起来,所以可以把整个 dp 表初始化为 1 ,然后就只需要判断长度大于 1 时的情况直接相加就行

填表顺序:从左到右

返回值:由于 dp[i] 中存储的是以 i 为结尾时的子串出现的次数,这就可能出现多次,例如“cac”

相同的子串只能统计一次,并且可以发现,以同一个字符结尾的子串只需要统计最长的即可,短的情况就包含在了长的情况,所以可以额外定义一个 hash 表来存储最终的答案,最后只需返回 hash 表中的所有和即可

class Solution {
    public int findSubstringInWraproundString(String s) {
        int n = s.length();
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        //表示 26 个字母
        int[] hash = new int[26];
        char[] chars = s.toCharArray();
        for(int i = 1;i < n;i++){
            if((chars[i] == (chars[i - 1] + 1)) || (chars[i] == 'a'&&chars[i - 1] == 'z')){
                dp[i] += dp[i - 1];
            }
        }
        int ret = 0;
        for(int i = 0;i < n;i++){
            //更新为以当前字符为结尾最长子串的数量
            hash[chars[i] - 'a'] = Math.max(hash[chars[i] - 'a'],dp[i]);
        }
        for(int x : hash) ret += x;
        return ret;
    }
}
相关文章
|
数据采集 机器学习/深度学习 算法框架/工具
利用Python实现基于图像识别的自动化数据采集系统
本文介绍了如何利用Python编程语言结合图像识别技术,构建一个自动化的数据采集系统。通过分析图像内容,实现对特定信息的提取和识别,并将其转化为结构化数据,从而实现高效、准确地采集需要的信息。本文将详细讨论系统的设计思路、技术实现以及应用场景。
【计算机网络】第三章 数据链路层(可靠传输)
【计算机网络】第三章 数据链路层(可靠传输)
|
IDE Shell 网络安全
使用ESC服务器配置code-server
使用ESC服务器来配置code-server服务(在线VSCode编辑器)
1502 1
使用ESC服务器配置code-server
|
安全 Java 程序员
Spring框架的核心特性是什么?
【4月更文挑战第30天】Spring 的特性
926 0
|
12月前
|
JSON 前端开发 Java
Spring MVC——获取参数和响应
本文介绍了如何在Spring框架中通过不同的注解和方法获取URL参数、上传文件、处理cookie和session、以及响应不同类型的数据。具体内容包括使用`@PathVariable`获取URL中的参数,使用`MultipartFile`上传文件,通过`HttpServletRequest`和`@CookieValue`获取cookie,通过`HttpSession`和`@SessionAttribute`获取session,以及如何返回静态页面、HTML代码片段、JSON数据,并设置HTTP状态码和响应头。
211 1
Spring MVC——获取参数和响应
|
12月前
|
Java 关系型数据库 MySQL
如何使用 maven 创建一个 Spring Boot项目
Maven 是一个强大的项目管理工具,通过配置 `pom.xml` 文件自动获取所需的 jar 包,提高开发效率。其核心功能包括项目构建和依赖管理。项目构建支持编译、测试、打包和发布等流程,而依赖管理则通过中央仓库、本地仓库和私有服务器获取和管理项目依赖。示例中展示了如何创建第一个 SpringBoot 项目并实现简单接口。
309 1
如何使用 maven 创建一个 Spring Boot项目
|
12月前
|
JSON 前端开发 Java
Spring MVC详解(上)
本文介绍了MVC架构及其在Spring MVC框架中的应用。MVC将应用程序分为模型、视图和控制器三部分,分别负责数据处理、用户界面展示和请求处理。Spring MVC作为MVC模式的具体实现,不仅是一个web框架,还提供了强大的功能支持,如URL路由映射、参数传递、JSON数据处理、文件上传等。文章详细讲解了如何在Spring MVC中使用`@RequestMapping`、`@RequestParam`、`@RequestBody`、`@PathVariable`等注解来处理HTTP请求,并展示了具体的代码示例和操作步骤。
138 1
|
存储 算法 Java
深入解析 Java 虚拟机:内存区域、类加载与垃圾回收机制
本文介绍了 JVM 的内存区域划分、类加载过程及垃圾回收机制。内存区域包括程序计数器、堆、栈和元数据区,每个区域存储不同类型的数据。类加载过程涉及加载、验证、准备、解析和初始化五个步骤。垃圾回收机制主要在堆内存进行,通过可达性分析识别垃圾对象,并采用标记-清除、复制和标记-整理等算法进行回收。此外,还介绍了 CMS 和 G1 等垃圾回收器的特点。
287 0
深入解析 Java 虚拟机:内存区域、类加载与垃圾回收机制
|
消息中间件 缓存 NoSQL
15)如何保证缓存和数据库之间的数据一致性
15)如何保证缓存和数据库之间的数据一致性
183 1
|
安全 Ubuntu Linux
在Linux中,如何进行FTP服务器配置?
在Linux中,如何进行FTP服务器配置?