目录
引言:
例题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.返回值。希望友友们看完本章后,自己理解一下子数组问题和子序列问题的差别。
例题1:最长递增子序列
链接:最长递增子序列
题目简介:
给你一个整数数组 nums
,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]
是数组 [0,3,1,6,2,2,7]
的子序列。
解法(动态规划):
1. 状态表示:
这里和子数组的表示方法倒是差不多。
dp[i] 表示:以i 位置元素为结尾的所有⼦序列中,最长递增子序列的长度。
2.状态转移方程:
推状态转移方程时可以画图帮助我们理解,下面这些情况可以大致分为两种,一种就只有一个i还有一种i会跟在i - 1,2,3的某一个后面(子序列)。
对于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
派生出来的序列。
解法(动态规划):
这道题和最长递增子序列有⼀些相似,但仔细读题就会发现,本题的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值要取哪一个呢?
其实取最后一个即可,因为最后一个肯定大于等于前面几个的长度。
因此,这⾥可以选择使⽤哈希表做优化。我们可以把【元素, 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]
的一个子序列)
解法(动态规划):
1. 状态表示:
2.状态转移方程:
设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.返回值:
因此返回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)文章来源:https://www.toymoban.com/news/detail-839269.html
例题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
是等差的。
解法(动态规划):
1. 状态表示:
和上一题一样,一维的dp表不能解决问题,dp[i][j] 表示:以i 位置以及j位置的元素为结尾的所有的子序列中,最长的等差序列的长度。规定⼀下i < j 。
2.状态转移方程:
设nums[i] = b, nums[j] = c ,那么这个序列的前⼀个元素就是a = 2 * b - c 。我们根据a的情况讨论:这里和例题3的分析差不多就直接给图了。
优化点:我们发现,在状态转移⽅程中,我们需要确定a 元素的下标。因此我们可以将所有的元素+ 下标绑定在⼀起,放到哈希表中,这里有两种策略:
(1)在dp 之前,放⼊哈希表中。这是可以的,但是需要将下标形成⼀个数组放进哈希表中。这样 时间复杂度较高,我帮⼤家试过了,超时。
(2)⼀边dp ,⼀边保存。这种方式,我们仅需保存最近的元素的下标,不用保存下标数组。但是 ⽤这种⽅法的话,我们在遍历顺序那里,先固定倒数第⼆个数(i),再遍历倒数第⼀个数(j)。这样就可以在i 使用完时候,将nums[i] 扔到哈希表中。✅
3.初始化:
将所有位置初始化为2。
4.填表顺序:
因为这里要保证去相同a下标k的最大值。
下图为固定倒数第一个数(j),枚举倒数第二个数。这样就不能保证跟新dp表时用到的a为在i前面的。红色部分为a可能出现的地方。
所以我们采用先固定倒数第⼆个数,然后枚举倒数第⼀个数如下图,这样a就只能在i的前面。
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 整数。
解法(动态规划):
1. 状态表示:
dp[i][j] 表⽰:以i 位置以及j 位置的元素为结尾的所有的⼦序列中,等差子序列的个数。规定⼀下i < j 。这一类问题基本都这样。
2.状态转移方程:
设nums[i] = b, nums[j] = c ,那么这个序列的前⼀个元素就是a = 2 * b - c 。我们根据a的情况讨论:(还是这张图非常重要)
(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模板网!