当前位置:   article > 正文

【算法专题】动态规划之子序列问题

【算法专题】动态规划之子序列问题

动态规划 - - - 子序列问题(数组中不连续的一段)

1. 最长递增子序列

题目链接 -> Leetcode -300.最长递增子序列

Leetcode -300.最长递增子序列

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

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

示例 1:
输入:nums = [10, 9, 2, 5, 3, 7, 101, 18]
输出:4
解释:最长递增子序列是[2, 3, 7, 101],因此长度为 4 。

示例 2:
输入:nums = [0, 1, 0, 3, 2, 3]
输出:4

示例 3:
输入:nums = [7, 7, 7, 7, 7, 7, 7]
输出:1

提示:

  • 1 <= nums.length <= 2500
  • 10^4 <= nums[i] <= 10^4

思路:

  1. dp[i] 表示:以 i 位置元素为结尾的「所有子序列」中,最长递增子序列的长度;
  2. 状态转移方程:对于 dp[i] ,我们可以根据「子序列的构成方式」,进行分类讨论:
  • 子序列长度为 1 :只能自己了,此时 dp[i] = 1 ;
  • 子序列长度大于 1 : nums[i] 可以跟在前面任何⼀个数后面形成子序列。设前面的某一个数的下标为 j ,其中 0 <= j <= i - 1 。只要 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];

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

代码如下:

		class Solution {
		public:
		    int lengthOfLIS(vector<int>& nums)
		    {
		        // 动态规划
		        // dp[i] 表示:以 i 位置元素为结尾的「所有子序列」中,最长递增子序列的长度
		        vector<int> dp(nums.size(), 1);
		        int ret = 0;
		        for (int i = nums.size() - 1; i >= 0; i--)
		        {
		            for (int j = i + 1; j < nums.size(); j++)
		            {
		                if (nums[j] > nums[i])
		                {
		                    dp[i] = max(dp[j] + 1, dp[i]);
		                }
		            }
		            ret = max(dp[i], ret);
		        }
		        return ret;
		    }
		};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

2. 摆动序列

题目链接 -> Leetcode -376.摆动序列

Leetcode -376.摆动序列

题目:如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如,[1, 7, 4, 9, 2, 5] 是一个 摆动序列 ,因为差值(6, -3, 5, -7, 3) 是正负交替出现的。

相反,[1, 4, 7, 2, 5] 和[1, 7, 4, 5, 5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。

给你一个整数数组 nums ,返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1:
输入:nums = [1, 7, 4, 9, 2, 5]
输出:6
解释:整个序列均为摆动序列,各元素之间的差值为(6, -3, 5, -7, 3) 。

示例 2:
输入:nums = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]
输出:7
解释:这个序列包含几个长度为 7 摆动序列。
其中一个是[1, 17, 10, 13, 10, 16, 8] ,各元素之间的差值为(16, -7, 3, -3, 6, -8) 。

示例 3:
输入:nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
输出:2

提示:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

思路:

  1. 状态表示:这里我们选择比较常用的方式,以某个位置为结尾,结合题目要求,定义一个状态表示:dp[i] 表示「以 i 位置为结尾的最长摆动序列的长度」。
    但是,问题来了,如果状态表示这样定义的话,以 i 位置为结尾的最长摆动序列的长度我们没法从之前的状态推导出来。因为我们不知道前一个最长摆动序列的结尾处是递增的,还是递减的。因此,我们需要状态表示能表示多一点的信息:要能让我们知道这一个最长摆动序列的结尾是递增的还是递减的。

所以我们应该定义两个 dp 表:

  • f[i] 表示:以 i 位置元素为结尾的所有的子序列中,最后一个位置呈现「上升趋势」的最长摆动序列的长度;
  • g[i] 表示:以 i 位置元素为结尾的所有的子序列中,最后一个位置呈现「下降趋势」的最长摆动序列的长度;
  1. 状态转移方程:由于子序列的构成比较特殊, i 位置为结尾的子序列,前一个位置可以是 [0, i - 1] 的任意位置,因此设 j 为 [0, i - 1] 区间内的某一个位置。
  • 对于 f[i] ,我们可以根据「子序列的构成方式」,进行分类讨论:
    i. 子序列长度为 1 :只能自己了,此时 f[i] = 1;这种情况不需要处理,我们在初始化的时候将 dp 表初始化为 1 即可 ;
    ii. 子序列长度大于 1 :因为结尾要呈现上升趋势,因此需要 nums[j] < nums[i] 。在满足这个条件下, j 结尾需要呈现下降状态,最长的摆动序列就是 g[j] + 1 。因此我们要找出所有满足条件下的最大的 g[j] + 1 。

综上,因为题目需要返回的是最长子序列的长度所以 f[i] 的状态转移方程为 f[i] = max(g[j] + 1, f[i]) ,注意使用 g[j] 时需要判断;

  • 对于 g[i] ,我们可以根据「子序列的构成方式」,进行分类讨论:
    i. 子序列长度为 1 :只能自己了,此时 g[i] = 1 ;这种情况不需要处理,我们在初始化的时候将 dp 表初始化为 1 即可 ;
    ii. 子序列长度大于 1 :因为结尾要呈现下降趋势,因此需要 nums[j] > nums[i] 。在满足这个条件下, j 结尾需要呈现上升状态,因此最长的摆动序列就是 f[j] + 1 。因此我们要找出所有满足条件下的最大的 f[j] + 1 。

综上, g[i] = max(f[j] + 1, g[i]) ,注意使用 f[j] 时需要判断;

  1. 返回值:应该返回「两个 dp 表里面的最大值」,我们可以在填表的时候,顺便更新⼀个「最大值」;

代码如下:

		class Solution {
		public:
		    int wiggleMaxLength(vector<int>& nums) 
		    {
		        int n = nums.size();
		
		        // f 表存最后呈现“上升”趋势的最长摆动子序列的长度
		        // g 表存最后呈现“下降”趋势的最长摆动子序列的长度
		        vector<int> f(n, 1), g(n, 1);
		
		        int ans = 1;
		        for(int i = 1; i < n; i++)
		        {
		            for(int j = i - 1; j >= 0; j--)
		            {
		                // 如果是上升趋势,f[i] 就是 g 表中的最长摆动子序列的长度 + 1,因为 g 表是呈下降趋势的;下同
		                if(nums[i] > nums[j]) f[i] = max(g[j] + 1, f[i]);
		                else if(nums[i] < nums[j]) g[i] = max(f[j] + 1, g[i]);
		            }
		
		            ans = max(g[i], max(f[i], ans));
		        }
		        return ans;
		    }
		};
  • 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

3. 最长递增子序列的个数

题目链接 -> Leetcode -673.最长递增子序列的个数

Leetcode -673.最长递增子序列的个数

题目:给定一个未排序的整数数组 nums , 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

示例 1:
输入: [1, 3, 5, 4, 7]
输出 : 2
解释 : 有两个最长递增子序列,分别是[1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2 :
输入 : [2, 2, 2, 2, 2]
输出 : 5
解释 : 最长递增子序列的长度是1,并且存在5个子序列的长度为1,因此输出5。

提示 :

  • 1 <= nums.length <= 2000
  • -10^6 <= nums[i] <= 10^6

思路:

  1. 状态表示:先尝试定义一个状态:以 i 为结尾的最长递增子序列的「个数」。那么问题就来了,我们都不知道以 i 为结尾的最长递增子序列的「长度」是多少,我怎么知道最长递增子序列的个数呢?

因此,我们解决这个问题需要两个状态,一个是「长度」,一个是「个数」:

  • len[i] 表示:以 i 为结尾的最长递增子序列的长度;
  • count[i] 表示:以 i 为结尾的最长递增子序列的个数;
  1. 状态转移方程:求个数之前,我们得先知道长度,因此先看 len[i] :
  • 在求 i 结尾的最长递增序列的长度时,我们已经知道 [0, i - 1] 区间上的 len[j] 信息,用 j 表示 [0, i - 1] 区间上的下标;
  • 我们需要的是递增序列,因此 [0, i - 1] 区间上的 nums[j] 只要能和 nums[i] 构成上升序列,那么就可以更新 dp[i] 的值,此时最长长度为 dp[j] + 1 ;
  • 我们要的是 [0, i - 1] 区间上所有情况下的最大值。

综上所述,对于 len[i] ,我们可以得到状态转移方程为:

  • len[i] = max(len[j] + 1, len[i]) ,其中 0 <= j < i ,并且 nums[j] < nums[i];

在知道每一个位置结尾的最长递增子序列的长度时,我们来看看能否得到 count[i] :

  • 我们此时已经知道 len[i] 的信息,还知道 [0, i - 1] 区间上的 count[j] 信息,用 j 表示 [0, i - 1] 区间上的下标;
  • 我们可以再遍历⼀遍 [0, i - 1] 区间上的所有元素,只要能够构成上升序列,并且上升序列的长度等于 dp[i] ,那么我们就把 count[i] 加上 count[j] 的值。这样循环一遍之后,count[i] 存的就是我们想要的值。

综上所述,对于 count[i] ,我们可以得到状态转移方程为:

  • count[i] += count[j] ,其中 0 <= j < i ,并且 nums[j] < nums[i] && dp[j] + 1 == dp[i] ;
  1. 返回值:用 retlen 表示最终的最长递增子序列的长度。根据题目要求,我们应该返回所有长度等于 retlen 的子序列的个数;

代码如下:

		class Solution {
		public:
		    int findNumberOfLIS(vector<int>& nums)
		    {
		        int n = nums.size(); 
		
		        // len[i] 表示以 i 位置结尾的最长递增子序列的长度
		        // count[i] 表示以 i 位置结尾的最长递增子序列的个数
		        vector<int> len(n, 1), count(n, 1);
		        int retlen = 1, retcount = 1;
		
		        for (int i = 1; i < n; i++)
		        {
		            for (int j = i - 1; j >= 0; j--)
		            {
		                if (nums[i] > nums[j])
		                {
		                    // 贪心
		                    if (len[j] + 1 > len[i])
		                    {
		                        len[i] = len[j] + 1;
		                        count[i] = count[j];
		                    }
		                    else if (len[j] + 1 == len[i])
		                    {
		                        count[i] += count[j];
		                    }
		                }
		            }
		
		            // 贪心
		            if (retlen == len[i])
		            {
		                retcount += count[i];
		            }
		            else if (len[i] > retlen)
		            {
		                retlen = len[i];
		                retcount = count[i];
		            }
		        }
		        return retcount;
		    }
		};
  • 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
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

4. 最长数对链

题目链接 -> Leetcode -646.最长数对链

Leetcode -646.最长数对链

题目:给你一个由 n 个数对组成的数对数组 pairs ,其中 pairs[i] = [lefti, righti] 且 lefti < righti 。
现在,我们定义一种 跟随 关系,当且仅当 b < c 时,数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。
找出并返回能够形成的 最长数对链的长度 。
你不需要用到所有的数对,你可以以任何顺序选择其中的一些数对来构造。

示例 1:
输入:pairs = [[1, 2], [2, 3], [3, 4]]
输出:2
解释:最长的数对链是[1, 2] ->[3, 4] 。

示例 2:
输入:pairs = [[1, 2], [7, 8], [4, 5]]
输出:3
解释:最长的数对链是[1, 2] ->[4, 5] ->[7, 8] 。

提示:

  • n == pairs.length
  • 1 <= n <= 1000
  • -1000 <= lefti < righti <= 1000

思路:本题思路与第一题 最长递增子序列 的思路类似,我们只需要将数对按照第一个元素排一下序即可处理;

代码如下:

		class Solution {
		public:
		    int findLongestChain(vector<vector<int>>& pairs) 
		    {
		        sort(pairs.begin(), pairs.end()); // 对第一个元素排序
		
		        int n = pairs.size();
		        vector<int> dp(n, 1);
		        int ans = 1;
		
		        // dp[i] 表⽰以 i 位置的数对为结尾时,最⻓数对链的⻓度
		        for(int i = 1; i < n; i++)
		        {
		            for(int j = i - 1; j >= 0; j--)
		            {
		                if(pairs[i][0] > pairs[j][1]) dp[i] = max(dp[j] + 1, dp[i]);
		            }
		            ans = max(dp[i], ans);
		        }
		        return ans;
		    }
		};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

5. 最长定差子序列

题目链接 -> Leetcode -1218.最长定差子序列

Leetcode -1218.最长定差子序列

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

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

示例 1:
输入:arr = [1, 2, 3, 4], difference = 1
输出:4
解释:最长的等差子序列是[1, 2, 3, 4]。

示例 2:
输入:arr = [1, 3, 5, 7], difference = 1
输出:1
解释:最长的等差子序列是任意单个元素。

示例 3:
输入:arr = [1, 5, 7, 8, 5, 3, 4, 2, 1], difference = -2
输出:4
解释:最长的等差子序列是[7, 5, 3, 1]。

提示:

  • 1 <= arr.length <= 10^5
  • -10^4 <= arr[i], difference <= 10^4

思路:

  1. 状态表示:
  • dp[i] 表示:以 i 位置的元素为结尾所有的子序列中,最长的等差子序列的长度。
  1. 状态转移方程:对于 dp[i] ,上一个定差子序列的取值定为 arr[i] - difference 。只要找到以上一个数字为结尾的定差子序列长度的 dp[arr[i] - difference] ,然后加上 1 ,就是以 i 为结尾的定差子序列的长度。

因此,这里可以选择使用哈希表做优化。我们可以把「元素, dp[j] 」绑定,放进哈希表中。甚至不用创建 dp 数组,直接在哈希表中做动态规划。

  1. 返回值:根据「状态表示」,返回整个 dp 表中的最大值;

代码如下:

		class Solution {
		public:
		    int longestSubsequence(vector<int>& arr, int difference) 
		    {
		        // dp[i] 表示:以 i 位置的元素为结尾所有的⼦序列中,最长的等差子序列的长度
		        unordered_map<int, int> hash;   // arr[i], dp[i]
		        hash[arr[0]] = 1;
		        int n = arr.size();
		        int ans = 1;
		
		        for(int i = 1; i < n; i++)
		        {
		            hash[arr[i]] = hash[arr[i] - difference] + 1;
		            ans = max(hash[arr[i]], ans);
		        }
		
		        return ans;
		    }
		};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

6. 最长的斐波那契子序列的长度

题目链接 -> Leetcode -873.最长的斐波那契子序列的长度

Leetcode -873.最长的斐波那契子序列的长度

题目:如果序列 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:
输入 : arr = [1, 2, 3, 4, 5, 6, 7, 8]
输出 : 5
解释 : 最长的斐波那契式子序列为[1, 2, 3, 5, 8] 。

示例 2:
输入 : arr = [1, 3, 7, 11, 12, 14, 18]
输出 : 3
解释 : 最长的斐波那契式子序列有[1, 11, 12]、[3, 11, 14] 以及[7, 11, 18] 。

提示:

  • 3 <= arr.length <= 1000
  • 1 <= arr[i] < arr[i + 1] <= 10^9

思路:

  1. 状态表示:这里我们选择比较常用的方式,以某个位置为结尾,结合题目要求,定义一个状态表示:dp[i] 表示:以 i 位置元素为结尾的「所有子序列」中,最长的斐波那契子数列的长度。

但是这里有一个非常致命的问题,那就是我们无法确定 i 结尾的斐波那契序列的样子。这样就会导致我们无法推导状态转移方程,因此我们定义的状态表示需要能够确定一个斐波那契序列。

根据斐波那契数列的特性,我们仅需知道序列里面的最后两个元素,就可以确定这个序列的样子。因此,我们修改我们的状态表示为:

  • dp[i][j] 表示:以 i 位置以及 j 位置的元素为结尾的所有的子序列中,最长的斐波那契子序列的长度。规定: i < j.
  1. 状态转移方程:设 nums[i] = b, nums[j] = c ,那么这个序列的前一个元素就是 a = c - b 。我们根据 a 的情况讨论:
  • a 存在,下标为 k ,并且 a < b :此时我们需要以 k 位置以及 i 位置元素为结尾的最长斐波那契子序列的长度,然后再加上 j 位置的元素即可。于是 dp[i][j] = dp[k][i] + 1 ;
  • a 存在,但是 b < a < c :此时只能两个元素自己了, dp[i][j] = 2 ;
  • a 不存在:此时依旧只能两个元素自己了, dp[i][j] = 2 ;

综上,状态转移方程分情况讨论即可。

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

  1. 返回值:因为不知道最终结果以谁为结尾,因此返回 dp 表中的最大值 ret ;但是 ret 可能小于 3 ,小于 3 的话说明不存在;因此需要判断一下。

代码如下:

		class Solution {
		public:
		    int lenLongestFibSubseq(vector<int>& arr)
		    {
		        int n = arr.size();
		        unordered_map<int, int> hash;   // arr[i] - i ,将数组中的元素与下标绑定放入哈希表中
		        for (int i = 0; i < n; i++) hash[arr[i]] = i;
		
		        vector<vector<int>> dp(n, vector<int>(n, 2));
		        int ans = 2;
		
		        // dp[j][i] 表示以 j 和 i 位置的元素为结尾的所有子序列中,最长的斐波那契子序列的长度
		        for (int i = 2; i < n; i++) // 固定 i 在后
		        {
		            for (int j = i - 1; j >= 1; j--) //固定 j 在前
		            {
		                int tp = arr[i] - arr[j];
		                if (tp < arr[j] && hash.count(tp)) dp[j][i] = dp[hash[tp]][j] + 1;
		
		                ans = max(dp[j][i], ans);
		            }
		            hash[arr[i]] = i;
		        }
		
		        return ans < 3 ? 0 : ans;
		    }
		};
  • 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
  • 27

7. 最长等差数列

题目链接 -> Leetcode -1027.最长等差数列

Leetcode -1027.最长等差数列

题目:给你一个整数数组 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:
输入:nums = [3, 6, 9, 12]
输出:4
解释:
整个数组是公差为 3 的等差数列。

示例 2:
输入:nums = [9, 4, 7, 2, 10]
输出:3
解释:
最长的等差子序列是[4, 7, 10]。

示例 3:
输入:nums = [20, 1, 15, 3, 10, 5, 8]
输出:4
解释:
最长的等差子序列是[20, 15, 10, 5]。

提示:

  • 2 <= nums.length <= 1000
  • 0 <= nums[i] <= 500

思路:本题思路与上题思路类似,只是在推前一个元素的方法不一样,其中本题:设 nums[i] = b, nums[j] = c ,那么这个序列的前一个元素就是 a = 2 * b - c ;接下来我们和上题根据 a 的情况讨论,这里就不再做讨论。

代码如下:

		class Solution {
		public:
		    int longestArithSeqLength(vector<int>& nums) 
		    {
		        int n = nums.size();
		        unordered_map<int, int> hash;   // nums[i], i
		        //for(int i = 0; i < n; i++) hash[nums[i]] = i;
		        hash[nums[0]] = 0;
		
		        int ans = 2;
		        vector<vector<int>> dp(n, vector<int>(n, 2));
		
		        // dp[i][j] 表示:以 i 位置以及 j 位置的元素为结尾的所有的⼦序列中,最长的等差序列的⻓度。规定 i < j
		        for(int i = 1; i < n; i++) // 固定倒数第二个数
		        {
		            for(int j = i + 1; j < n; j++)  // 固定倒数第一个数
		            {
		                // 求出以 i 和 j 位置结尾的子序列中,以它们为等差数列的前一个数
		                int tp = 2 * nums[i] - nums[j];
		                if(hash.count(tp)) 
		                {
		                    dp[i][j] = dp[hash[tp]][i] + 1;
		                }
		
		                ans = max(ans, dp[i][j]);
		            }
		            
		            // 一边做 dp 一边更新hash数组;以便多个 tp 元素重复时,hash[tp]找到的是离 i 最近的下标
		            hash[nums[i]] = i;
		        }
		
		        return ans;
		    }
		};
  • 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
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

8. 等差数列划分Ⅱ - 子序列

题目链接 -> 等差数列划分Ⅱ - 子序列

Leetcode -446.等差数列划分Ⅱ - 子序列

题目:给你一个整数数组 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:
输入:nums = [2, 4, 6, 8, 10]
输出:7
解释:所有的等差子序列为:
[2, 4, 6]
[4, 6, 8]
[6, 8, 10]
[2, 4, 6, 8]
[4, 6, 8, 10]
[2, 4, 6, 8, 10]
[2, 6, 10]

示例 2:
输入:nums = [7, 7, 7, 7, 7]
输出:16
解释:数组中的任意子序列都是等差子序列。

提示:

  • 1 <= nums.length <= 1000
  • -2^31 <= nums[i] <= 2^31 - 1

思路:

本题与最长等差数列的区别是,最长等差数列求的是最长等差数列的长度,本题求的是等差数列的数目;所以思路我们也是类似的:

  1. 状态表示:dp[i][j] 表示:以 i 位置以及 j 位置的元素为结尾的所有的子序列中,等差子序列的个数。规定⼀下 i < j.

  2. 状态转移方程:设 nums[i] = b, nums[j] = c ,那么这个序列的前一个元素就是 a = 2 * b - c 。我们根据 a 的情况讨论:

  • a 存在,下标为 k ,并且 a < b :此时我们知道以 k 元素以及 i 元素结尾的等差序列的个数 dp[k][i] ,在这些子序列的后面加上 j 位置的元素依旧是等差序列。但是这里会多出来一个以 k, i, j 位置的元素组成的新的等差序列,因此 dp[i][j] = dp[k][i] + 1 ;
  • 因为 a 可能有很多个,我们需要全部累加起来。

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

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

代码如下:

		class Solution {
		public:
		    int numberOfArithmeticSlices(vector<int>& nums) 
		    {
		        int n = nums.size();
		        // 将数组的元素和下标数组绑定在一起放入哈希表中,因为相同的元素会有不同的下标
		        unordered_map<long long, vector<int>> hash;  
		        for(int i = 0; i < n; i++) hash[nums[i]].push_back(i);
		
		        vector<vector<int>> dp(n, vector<int>(n));
		        int count = 0;
		
		        for(int i = 1; i < n; i++) // 枚举倒数第二个数
		        {
		            for(int j = i + 1; j < n; j++) // 枚举倒数第一个数
		            {
		                long long tp = (long long)2 * nums[i] - nums[j];
		                if(hash.count(tp)) 
		                {
		                    // 遍历 tp 元素的下标数组,tp 的下标需要小于 i
		                    for(auto& k : hash[tp])
		                    {
		                        // 需要 += ,是因为要确定以 i、j 为结尾的元素前面的等差数列个数,就要用以 k、i 为结尾的元素前面的等差数列个数再加上1;因为以 k、i 为结尾的元素前面的等差数列再加上 j 的元素,也能构成数量相同的等差数列个数,而且多了 k、i、j 这一组等差数列,所以要多加1
		                        if(k < i) dp[i][j] += dp[k][i] + 1;
		                    }
		                }
		                count += dp[i][j];
		            }
		        }
		
		        return count;
		    }
		};
  • 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
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小蓝xlanll/article/detail/102451?site
推荐阅读
相关标签
  

闽ICP备14008679号