动态规划学习——子序列问题

目录

​编辑

一，最长定差子序列

1.题目

2，题目接口

 3，解题思路及其代码

---

一，最长定差子序列

1.题目

给你一个整数数组 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]。

2，题目接口

class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {}
};

 3，解题思路及其代码

1.状态转移方程:    

这道题要我们求的是最长定差子序列问题，不再是最长子序列。这里的关键便是定差，也就是说在我们知道差以后我们便可以知道第2个数的值。我们的dp[i] 表示为以i位置为结尾的最长等差子序列。

 2.初始化：

 当我们的每个nums[i]单独构成一个子序列时长度为1，所以我们初始化时边初始化为1即可。

在明确好这些后便可以写出如下代码：

class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {int n = arr.size();vector<int>dp(n,1);int Maxlenth = 1;for(int i = 0;i<n;i++){int num = arr[i]+difference;//找定差for( int j = i+1;j<n;j++){if(arr[j] == num){dp[j] = dp[i]+1;}}Maxlenth = max(Maxlenth,dp[i]);//每次都要更新一下最大值}return Maxlenth;}
};

但是，这个代码是过不了的。因为这个代码的时间复杂度为O(n^2)。所以我们要对这个代码做一些优化。优化的秘诀便是hash表：unordered_map。改进思路如下：

1.先创建一个hash表。

2.将arr里面的所有元素和元素的对应下标放到hash表中构成映射，arr[i]作key，下标作value。

现在改进代码如下：

class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {unordered_map<int,int> hash;//在hash表里做dpint n = arr.size();int Max = 1;hash[arr[0]] = 1;for(int i = 1;i<n;i++){hash[arr[i]] = hash[arr[i]-difference]+1;//如果arr[i]-difference那也会访问最后一个arr[i]-difference的值。因为hash的底层插入是头插Max = max(Max,hash[arr[i]]);}return Max;}
};

提交：过啦！！！