动态规划-子序列问题——1218.最长定差子序列

1.题目解析

题目来源：1218.最长定差子序列——力扣

测试用例

2.算法原理

1.状态表示

本题可以看作是寻找一个等差序列，并且公差给出，这里并不是普通的使用一个dp表，而是将arr与dp表同时存储于一个哈希表，arr[i]映射dp[i]，这样就可以只遍历符合等差序列的每个位置而不用遍历所有位置

2.状态转移方程

只需要找到符合等差序列的哈希表就直接对等差序列长度+1即可，即：hash[arr[i]] = hash[arr[i] - difference] + 1;

3.初始化

最小等差序列的长度为1，将第一个哈希表的位置置为1即可

4.填表顺序

从左到右只填写符合等差序列位置的值

5.返回值

返回哈希表的最大值

3.实战代码

class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {int n = arr.size();unordered_map<int,int> hash;//arr[i] - dp[i]hash[arr[0]] = 1;int ret = 1;for(int i = 1;i < n;i++){hash[arr[i]] = hash[arr[i] - difference] + 1;ret = max(ret,hash[arr[i]]);}return ret;}
};