动态规划课堂5-----子序列问题(动态规划 + 哈希表)

这篇具有很好参考价值的文章主要介绍了动态规划课堂5-----子序列问题(动态规划 + 哈希表)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

引言:

例题1:最长递增子序列

例题2:最长定差子序列

例题3:最长的斐波那契子序列的长度

例题4:最长等差数列

例题5:等差数列划分II-子序列

结语:


引言:

要想解决子序列问题那么就要理解子序列和子数组的区别,二者的定义如下。

子序列:是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

子数组:是数组中的一个连续部分[6,2,2,7] 是数组 [0,3,1,6,2,2,7] 的子数组。

本节和之前的分析思路一样还是考虑好1. 状态表示,2.状态转移方程,3.初始化,4.填表顺序,5.返回值。希望友友们看完本章后,自己理解一下子数组问题和子序列问题的差别。

动态规划课堂5-----子序列问题(动态规划 + 哈希表),动态规划,动态规划,算法,java,leetcode,哈希表,子序列

例题1:最长递增子序列

链接:最长递增子序列

题目简介:

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

动态规划课堂5-----子序列问题(动态规划 + 哈希表),动态规划,动态规划,算法,java,leetcode,哈希表,子序列

解法(动态规划):

 1. 状态表示:

这里和子数组的表示方法倒是差不多。

dp[i] 表示:以i 位置元素为结尾的所有⼦序列中,最长递增子序列的长度。

 2.状态转移方程:

推状态转移方程时可以画图帮助我们理解,下面这些情况可以大致分为两种,一种就只有一个i还有一种i会跟在i - 1,2,3的某一个后面(子序列)。

动态规划课堂5-----子序列问题(动态规划 + 哈希表),动态规划,动态规划,算法,java,leetcode,哈希表,子序列

对于dp[i] ,我们可以根据子序列的构成⽅式,进⾏分类讨论:

(1)子序列长度为1 :只能自己玩了,此时dp[i] = 1 。

(2)子序列长度大于1 : nums[i] 可以跟在前面任何⼀个数后面形成子序列。 设前面的某⼀个数的下标为j ,其中0 。只要nums[j] < nums[i] , i 位置元素跟在j 元素后⾯就可以形成递增序列,长度为dp[j] + 1 。因此,我们仅需找到满足要求的最大的dp[j] + 1 即可。

综上, dp[i] = max(dp[j] + 1, dp[i]) ,其中0 <= j <= i - 1 && nums[j] < nums[i]。

 3.初始化:

在求长度之类的dp问题一般可以直接把dp表都初始化成1,因为在我们的状态表示中长度至少为1.因此可以将dp 表内所有元素初始化为1 。

 4.填表顺序:

从左往右

 5.返回值: 

由于不知道最长递增子序列以谁结尾,因此返回dp 表里面的最大值。

代码如下:

class Solution {
    public int lengthOfLIS(int[] nums) {
        //1.创建 dp 表
        //2.初始化
        //3.填表
        //4.返回值
        int n = nums.length;
        int[] dp = new int[n];
        for(int i = 0;i < n;i++){
            dp[i] = 1;
        }
        int max = dp[0];
        for(int i = 1;i < n;i++){
            for(int j = i - 1;j >= 0;j--){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

时间复杂度:O(n^2)

空间复杂度:O(n)

接下来几题会用到动态规划 + 哈希表

例题2:最长定差子序列

链接:最长定差子序列

题目简介:

给你一个整数数组 arr 和一个整数 difference,请你找出并返回 arr 中最长等差子序列的长度,该子序列中相邻元素之间的差等于 difference 。

子序列 是指在不改变其余元素顺序的情况下,通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

动态规划课堂5-----子序列问题(动态规划 + 哈希表),动态规划,动态规划,算法,java,leetcode,哈希表,子序列

 解法(动态规划):

这道题和最长递增子序列有⼀些相似,但仔细读题就会发现,本题的arr.lenght⾼达10^5 ,使⽤O(N^2) 的lcs 模型⼀定会超时。那么,它有什么信息是不同于最长递增子序列呢?是定差。之前,我们只知道要递增,不知道前⼀个数应当是多少;现在我们可以计算出前⼀个数是多少了,就可以⽤数值来定义dp 数组的值,并形成状态转移。这样,就把已有信息有效地利用了起来。

 1. 状态表示:

dp[i] 表示:以i 位置的元素为结尾所有的子序列中,最长的等差子序列的长度。

 2.状态转移方程:

对于dp[i] ,上⼀个定差⼦序列的取值定为arr[i] - difference 。只要找到以上⼀个数字为结尾的定差⼦序列⻓度的dp[arr[i] - difference] ,然后加上1 ,就是以i为结尾的定差⼦序列的⻓度。

这里要考虑一个问题:如果在i前面有多个等于arr[i] - difference的dp值要取哪一个呢?

动态规划课堂5-----子序列问题(动态规划 + 哈希表),动态规划,动态规划,算法,java,leetcode,哈希表,子序列

 其实取最后一个即可,因为最后一个肯定大于等于前面几个的长度。

因此,这⾥可以选择使⽤哈希表做优化。我们可以把【元素, dp[j]】绑定,放进哈希表(会覆盖)中。甚⾄不⽤创建dp 数组,直接在哈希表中做动态规划。

 3.初始化:

刚开始的时候,需要把第⼀个元素放进哈希表中, hash[arr[0]] = 1。

 4.填表顺序:

从左往右

 5.返回值:

返回整个dp 表中的最⼤值

代码如下:

这里之所以不用 hash[arr[0]] = 1,是因为在下面put的写法中已经包含了。

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        //在哈希表里面做动态规划
        Map<Integer,Integer> map = new HashMap<>();
        int ret = 1;
        for(int x:arr){
            map.put(x,map.getOrDefault(x - difference,0) + 1);
            ret = Math.max(ret,map.get(x));
        }
        return ret;
    }
}

 时间复杂度:O(n) 

 空间复杂度:O(n)

例题3:最长的斐波那契子序列的长度

链接:最长的斐波那契子序列的长度

题目简介:

如果序列 X_1, X_2, ..., X_n 满足下列条件,就说它是 斐波那契式 的:

  • n >= 3
  • 对于所有 i + 2 <= n,都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列 arr ,找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在,返回  0 。

(回想一下,子序列是从原序列 arr 中派生出来的,它从 arr 中删掉任意数量的元素(也可以不删),而不改变其余元素的顺序。例如, [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列)

动态规划课堂5-----子序列问题(动态规划 + 哈希表),动态规划,动态规划,算法,java,leetcode,哈希表,子序列

 解法(动态规划):

 1. 状态表示:

动态规划课堂5-----子序列问题(动态规划 + 哈希表),动态规划,动态规划,算法,java,leetcode,哈希表,子序列

 2.状态转移方程:

动态规划课堂5-----子序列问题(动态规划 + 哈希表),动态规划,动态规划,算法,java,leetcode,哈希表,子序列

设nums[i] = b, nums[j] = c ,那么这个序列的前⼀个元素就是a = c - b 。我们根据a 的情况讨论:

(1)a 存在,下标为k ,并且a < b :此时我们需要以k 位置以及i 位置元素为结尾的最⻓斐波那契⼦序列的⻓度,然后再加上j位置的元素即可。于是dp[i][j] = dp[k][i] + 1。

(2)a 存在,但是b < a < c :此时只能两个元素自己玩了, dp[i][j] = 2 。

(3)a 不存在:此时依旧只能两个元素自己玩了, dp[i][j] = 2 。

优化点:我们发现,在状态转移⽅程中,我们需要确定a 元素的下标。因此我们可以在dp 之前,将所有的元素+下标绑定在⼀起,放到哈希表中。

 3.初始化:

可以将表⾥⾯的值都初始化为2

 4.填表顺序:

先固定最后⼀个数,然后枚举倒数第二个数。由于j > i 故表如下:

动态规划课堂5-----子序列问题(动态规划 + 哈希表),动态规划,动态规划,算法,java,leetcode,哈希表,子序列

 5.返回值:

因此返回dp 表中的最大值但是最大值可能小于3 ,小于3的话说明不存在。因此需要判断⼀下。

具体代码如下:

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        //1.创建 dp 表
        //2.初始化
        //3.填表
        //4.返回值
        Map<Integer,Integer> map = new HashMap<>();
        int n = arr.length;
        for(int i = 0;i < n;i++){
            map.put(arr[i],i);
        }
        int[][] dp = new int[n][n];
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                dp[i][j] = 2;
            }
        }
        int ret = 2;
        for(int j = 2;j < n;j++){
            for(int i = 1;i < j;i++){
                int a = arr[j] - arr[i];
                if(a < arr[i] && map.containsKey(a)){
                    dp[i][j] = dp[map.get(a)][i] + 1;
                }
                ret = Math.max(ret,dp[i][j]);
            }
        }
        return ret < 3 ? 0 : ret;
    }
}

时间复杂度:O(n^2)

空间复杂度:O(n^2)

例题4:最长等差数列

链接:最长等差数列

题目简介:

给你一个整数数组 nums,返回 nums 中最长等差子序列的长度

回想一下,nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ,且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]0 <= i < seq.length - 1) 的值都相同,那么序列 seq 是等差的。

动态规划课堂5-----子序列问题(动态规划 + 哈希表),动态规划,动态规划,算法,java,leetcode,哈希表,子序列

 解法(动态规划):

 1. 状态表示:

和上一题一样,一维的dp表不能解决问题,dp[i][j] 表示:以i 位置以及j位置的元素为结尾的所有的子序列中,最长的等差序列的长度。规定⼀下i < j 。

 2.状态转移方程:

设nums[i] = b, nums[j] = c ,那么这个序列的前⼀个元素就是a = 2 * b - c 。我们根据a的情况讨论:这里和例题3的分析差不多就直接给图了。

动态规划课堂5-----子序列问题(动态规划 + 哈希表),动态规划,动态规划,算法,java,leetcode,哈希表,子序列

动态规划课堂5-----子序列问题(动态规划 + 哈希表),动态规划,动态规划,算法,java,leetcode,哈希表,子序列

优化点:我们发现,在状态转移⽅程中,我们需要确定a 元素的下标。因此我们可以将所有的元素+ 下标绑定在⼀起,放到哈希表中,这里有两种策略:

(1)在dp 之前,放⼊哈希表中。这是可以的,但是需要将下标形成⼀个数组放进哈希表中。这样 时间复杂度较高,我帮⼤家试过了,超时。

(2)⼀边dp ,⼀边保存。这种方式,我们仅需保存最近的元素的下标,不用保存下标数组。但是 ⽤这种⽅法的话,我们在遍历顺序那里,先固定倒数第⼆个数(i),再遍历倒数第⼀个数(j)。这样就可以在i 使用完时候,将nums[i] 扔到哈希表中。✅

 3.初始化:

将所有位置初始化为2。

 4.填表顺序:

因为这里要保证去相同a下标k的最大值。

下图为固定倒数第一个数(j),枚举倒数第二个数。这样就不能保证跟新dp表时用到的a为在i前面的。红色部分为a可能出现的地方。

动态规划课堂5-----子序列问题(动态规划 + 哈希表),动态规划,动态规划,算法,java,leetcode,哈希表,子序列

所以我们采用先固定倒数第⼆个数,然后枚举倒数第⼀个数如下图,这样a就只能在i的前面。

动态规划课堂5-----子序列问题(动态规划 + 哈希表),动态规划,动态规划,算法,java,leetcode,哈希表,子序列

 5.返回值:

返回dp 表中的最大值

代码如下:

class Solution {
    public int longestArithSeqLength(int[] nums) {
        //1.创建 dp 表
        //2.初始化
        //3.填表
        //4.返回值
        Map<Integer,Integer> map = new HashMap<>();
        int n = nums.length;
        map.put(nums[0],0);
        int[][] dp = new int[n][n];
        for(int i = 0;i < n;i++){
            Arrays.fill(dp[i],2);
        }
        int ret = 2;
        for(int i = 1;i < n;i++){
            for(int j = i + 1;j < n;j++){
                int a = 2 * nums[i] - nums[j];
                if(map.containsKey(a)){
                    dp[i][j] = dp[map.get(a)][i] + 1;
                    ret = Math.max(ret,dp[i][j]);
                }
            }
            map.put(nums[i],i);
        }
        return ret;

    }
}

时间复杂度:O(n^2)

空间复杂度:O(n^2)

例题5:等差数列划分II-子序列

链接:等差数列划分II-子序列

题目简介:

给你一个整数数组 nums ,返回 nums 中所有 等差子序列 的数目。

如果一个序列中 至少有三个元素 ,并且任意两个相邻元素之差相同,则称该序列为等差序列。

  • 例如,[1, 3, 5, 7, 9][7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
  • 再例如,[1, 1, 2, 5, 7] 不是等差序列。

数组中的子序列是从数组中删除一些元素(也可能不删除)得到的一个序列。

  • 例如,[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。

题目数据保证答案是一个 32-bit 整数。

动态规划课堂5-----子序列问题(动态规划 + 哈希表),动态规划,动态规划,算法,java,leetcode,哈希表,子序列

  解法(动态规划):

 1. 状态表示:

dp[i][j] 表⽰:以i 位置以及j 位置的元素为结尾的所有的⼦序列中,等差子序列的个数。规定⼀下i < j 。这一类问题基本都这样。

 2.状态转移方程:

设nums[i] = b, nums[j] = c ,那么这个序列的前⼀个元素就是a = 2 * b - c 。我们根据a的情况讨论:(还是这张图非常重要)

动态规划课堂5-----子序列问题(动态规划 + 哈希表),动态规划,动态规划,算法,java,leetcode,哈希表,子序列

(1)a 存在,下标为k ,并且a < b :此时我们知道以k 元素以及i 元素结尾的等差序列的数dp[k][i] ,在这些⼦序列的后⾯加上j 位置的元素依旧是等差序列。但是这⾥会多出来⼀个以k, i, j 位置的元素组成的新的等差序列,因此dp[i][j] = dp[k][i] + 1。

(2)因为a 可能有很多个,我们需要全部累加起来。

综上, dp[i][j] += dp[k][i] + 1 。

优化点:我们发现,在状态转移⽅程中,我们需要确定a 元素的下标。因此我们可以在dp之前,将【所有元素+下标数组】绑定在⼀起,放到哈希表中。这⾥为何要保存下标数组,是因为我们要统计个数,所有的下标都需要统计,之前是覆盖。

 3.初始化:

初始化dp 表为0。

 4.填表顺序:

先固定倒数第⼀个数,然后枚举倒数第⼆个数(这里就不能先固定倒数第二个数,因为要的是各个情况的和而不是最大值)。

 5.返回值:

我们要统计所有的等差子序列,因此返回dp 表中所有元素的和。

代码如下:

这里特别说明一个,题目给出的数都是32位以内的但是相加减可能会越界(😭),有些例子越界后可能会正好形成等差数列从而报错(我替你们试过了😭😭😭),故要设置成long类型。

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        //1.创建 dp 表
        //2.初始化
        //3.填表
        //4.返回值
        Map<Long,List<Integer>> map = new HashMap<>();
        int n = nums.length;
        int[][] dp = new int[n][n];
        for(int i = 0;i < n;i++){
            long cmp = (long)nums[i];
            if(!map.containsKey(cmp)){
                map.put(cmp,new ArrayList<Integer>());
            }
            map.get(cmp).add(i);
        }
        int sum = 0;
        for(int j = 2;j < n;j++){
            for(int i = 1;i < j;i++){
                long a = 2L * nums[i] - nums[j];
                if(map.containsKey(a)){
                    for(int k : map.get(a)){
                        if(k < i){
                            dp[i][j] += dp[k][i] + 1;
                        }
                    }
                }
                sum += dp[i][j];
            }
        }
        return sum;

    }
}

时间复杂度:O(n^2)

空间复杂度:O(n^2)

结语:

其实写博客不仅仅是为了教大家,同时这也有利于我巩固知识点,和做一个学习的总结,由于作者水平有限,对文章有任何问题还请指出,非常感谢。如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注,这可以激励我写出更加优秀的文章。文章来源地址https://www.toymoban.com/news/detail-839269.html

到了这里,关于动态规划课堂5-----子序列问题(动态规划 + 哈希表)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法打卡day49|动态规划篇17| Leetcode 647. 回文子串、516.最长回文子序列

    Leetcode 647. 回文子串 题目链接:647. 回文子串 大佬视频讲解:647. 回文子串视频讲解  个人思路  这道题的dp数组有点难找到关联,以至于递归关系也不好找,所以看题解吧... 解法 动态规划 动规五部曲: 1.确定dp数组(dp table)以及下标的含义 一般在定义dp数组的时候 会根据题

    2024年04月22日
    浏览(50)
  • 【算法(四·三):动态规划思想——最长公共子序列问题】

    最长公共子序列(Longest Common Subsequence,简称LCS)问题是一种常见的字符串处理问题。它的**目标是找到两个或多个字符串中的最长公共子序列,这个子序列不需要是连续的,但字符在原始字符串中的相对顺序必须保持一致。**例如,考虑两个字符串\\\"ABCD\\\"和\\\"ACDF\\\",它们的最长公

    2024年04月13日
    浏览(50)
  • (Java) 算法——动态规划 最长公共子序列 图解

    遇到了用动态规划来求解最长公共子序列问题,算法这块儿比较薄弱,便想着在网上找现成的思路和代码,也算拾人牙慧,但有一点没想到,都已经22年了,关于LCS问题网上给出的答案如此一言难尽……,只有零散几篇对于 新手 来说比较友好,但也仅仅这样,好在自己花了点

    2023年04月08日
    浏览(47)
  • 算法小课堂(四)动态规划

    目录 一、概况 二、背包 2.0闫式dp分析法 2.1 0-1背包 朴素解法 滚动数组 2.2 完全背包 朴素解法 优化降维 滚动数组 2.3完全背包和0-1背包的区别与联系 2.4多重背包问题 朴素解法 二进制枚举优化 贪心算法 单调队列优化 2.5分组背包问题 朴素算法 优化降维 二进制枚举优化 三、线

    2023年04月27日
    浏览(57)
  • 【算法小课堂】动态规划

    动态规划相信大家都知道,动态规划算法也是新手在刚接触算法设计时很苦恼的问题,有时候觉得难以理解,但是真正理解之后,就会觉得动态规划其实并没有想象中那么难。网上也有很多关于讲解动态规划的文章,大多都是叙述概念,讲解原理,让人觉得晦涩难懂,即使一

    2024年01月25日
    浏览(43)
  • 动态规划课堂6-----回文串问题

    目录 引言: 例题1:回文子串 例题2:回文串分割IV 例题3:分割回文串II 例题4:最长回文子序列 例题5:让字符串成为回文串的最小插入次数 回文字符串  是正着读和倒过来读一样的字符串。 动态规划的回文串问题一般是把 子串 是否是回文串的信息保持在dp表里面,所以更

    2024年03月18日
    浏览(47)
  • LeetCode 2008. 出租车的最大盈利:动态规划 + 哈希表

    力扣题目链接:https://leetcode.cn/problems/maximum-earnings-from-taxi/ 你驾驶出租车行驶在一条有 n  个地点的路上。这 n  个地点从近到远编号为  1  到  n  ,你想要从 1  开到 n  ,通过接乘客订单盈利。你只能沿着编号递增的方向前进,不能改变方向。 乘客信息用一个下标从 0  开

    2024年02月04日
    浏览(48)
  • 动态规划课堂7-----两个数组的dp问题(等价代换)

    目录 引言: 例题1:最长公共子序列 例题2:不同的子序列 例题3:通配符匹配 例题4:正则表达式 结语: 本节我们就要进入 两个数组的dp问题 的学习,通过前面几个章节的学习,相信友友们对动态规划的解题步骤和代码编写步骤已经有了一定的了解(*/ω\*),接下来我会通过

    2024年03月22日
    浏览(39)
  • 【手撕算法|动态规划系列No.2】leetcode面试题 08.01. 三步问题

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月12日
    浏览(64)
  • LeetCode 1079. Letter Tile Possibilities【哈希表,回溯,动态规划,排列组合】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月10日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包