你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

【LeetCode每日一题】(动态规划)1218. 最长定差子序列

2021/11/5 22:37:18

文章目录

题目

一、解题思路

二、结果

1.注意点

2.C++代码

总结


题目

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference

一、解题思路

假设给定数组为 [1,5,3,6,5,7],等差 d=2,辅助数组为 dp,求解的过程如下:

遍历到 1,发现 1-2=-1 不在 dp 数组,记录 dp[1] = 1,表示以 1 结尾的等差数列只有 1 个数;
遍历到 5,发现 5-2=3 不在 dp 数组,记录 dp[5]=1;
遍历到 3,发现 3-2=1 在 dp 数组且以 1 结尾的等差数列长度为 1,所以,记录 dp[3]=dp[3-2]+1=2,表示以 3 结尾的等差数列长度为 2;
遍历到 6,发现 6-2=4 不在 dp 数组,记录 dp[6]=1;
遍历到 5,发现 5-2=3 在 dp 数组,记录 dp[5]=dp[5-2]+1=3;
遍历到 7,发现 7-2=5 在 dp 数组,记录 dp[7]=dp[7-2]+1=4;
取 dp 数组中的最大值,即 4,所以,最长等差子序列的长度为 4。
这其实就是动态规划的递推过程,所以,我们可以定义动态规划如下:

状态定义:dp[x] 表示以 x 结尾的最长等差子序列的长度;
状态转移:dp[x]=dp[x-d]+1;

二、结果

1.注意点

利用辅助数组存储序列等差项的个数;

注意理解dp[x]=dp[x-d]+1的推到,存在一个等差的就+1;

2.C++代码

代码如下(示例):

class Solution {
public:
    int longestSubsequence(vector<int> &arr, int difference) {
        int ans = 0;
        //创建dp数组来记录序列的个数
        unordered_map<int, int> dp;
        for (int v: arr) {
            dp[v] = dp[v - difference] + 1;
            ans = max(ans, dp[v]);
        }
        return ans;
    }
};


总结

题目完全可以用暴力去解决,但可能会超时,动态规划很难想到,要不断吸取经验,熟能生巧!!

加油加油,坚持坚持!!!