【算法挨揍日记】day32——1218. 最长定差子序列、873. 最长的斐波那契子序列的长度

逃离我推掉我的手 2024-02-18 12:33 42阅读 0赞

## 1218. 最长定差子序列 ##

[1218. 最长定差子序列][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 <= 105`
 *  `-104 <= arr[i], difference <= 104`

###  ###

### 解题思路： ###

算法思路：

这道题和  300. 最⻓递增⼦序列  有⼀些相似，但仔细读题就会发现，本题的  arr.lenght  ⾼达

10^5  ，使⽤  O(N^2)  的  lcs  模型⼀定会超时。

那么，它有什么信息是  300. 最⻓递增⼦序列  的呢？是定差。之前，我们只知道要递增，不知道前

⼀个数应当是多少；现在我们可以计算出前⼀个数是多少了，就可以⽤数值来定义  dp  数组的

值，并形成状态转移。这样，就把已有信息有效地利⽤了起来。

1.  状态表⽰：

dp\[i\]  表⽰：以  i  位置的元素为结尾所有的⼦序列中，最⻓的等差⼦序列的⻓度。

2.  状态转移⽅程：

对于  dp\[i\]  ，上⼀个定差⼦序列的取值定为  arr\[i\] - difference  。只要找到以上⼀个数

字为结尾的定差⼦序列⻓度的  dp\[arr\[i\] - difference\]  ，然后加上  1  ，就是以  i  为结

尾的定差⼦序列的⻓度。

因此，这⾥可以选择使⽤哈希表做优化。我们可以把「元素，  dp\[j\]  」绑定，放进哈希表中。甚

⾄不⽤创建  dp  数组，直接在哈希表中做动态规划。

3.  初始化：

刚开始的时候，需要把第⼀个元素放进哈希表中，  hash\[arr\[0\]\] = 1  。

4.  填表顺序：

根据「状态转移⽅程」，填表顺序应该是「从左往右」。

5.  返回值：

根据「状态表⽰」，返回整个  dp  表中的最⼤值

### 解题代码： ###

class Solution
    {
    public:
     int longestSubsequence(vector<int>& arr, int difference) 
     {
     // 创建⼀个哈希表
     unordered_map<int, int> hash; // {arr[i], dp[i]}
     hash[arr[0]] = 1; // 初始化
     int ret = 1;
     for(int i = 1; i < arr.size(); i++)
     {
     hash[arr[i]] = hash[arr[i] - difference] + 1;
     ret = max(ret, hash[arr[i]]);
     }
     return ret;
     }
    };

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

[873. 最长的斐波那契子序列的长度][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]` 的一个子序列）*

![e36c992b2c1b4cf096a5946f7a77b82a.png][]

### 解题思路： ###

算法思路：

1.  状态表⽰：

对于线性  dp  ，我们可以⽤「经验 + 题⽬要求」来定义状态表⽰：

i.  以某个位置为结尾，巴拉巴拉；

ii.  以某个位置为起点，巴拉巴拉。

这⾥我们选择⽐较常⽤的⽅式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表⽰：

dp\[i\]  表⽰：以  i  位置元素为结尾的「所有⼦序列」中，最⻓的斐波那契⼦数列的⻓度。

但是这⾥有⼀个⾮常致命的问题，那就是我们⽆法确定 i 结尾的斐波那契序列的样⼦。这样就会导

致我们⽆法推导状态转移⽅程，因此我们定义的状态表⽰需要能够确定⼀个斐波那契序列。

根据斐波那契数列的特性，我们仅需知道序列⾥⾯的最后两个元素，就可以确定这个序列的样⼦。

因此，我们修改我们的状态表⽰为：

dp\[i\]\[j\]  表⽰：以  i  位置以及  j  位置的元素为结尾的所有的⼦序列中，最⻓的斐波那契⼦

序列的⻓度。规定⼀下  i < j  。

2.  状态转移⽅程：

设  nums\[i\] = b, nums\[j\] = c  ，那么这个序列的前⼀个元素就是  a = c - b  。我们根

据  a  的情况讨论：

i.  a  存在，下标为  k  ，并且  a < b  ：此时我们需要以  k  位置以及  i  位置元素为结尾的

最⻓斐波那契⼦序列的⻓度，然后再加上  j  位置的元素即可。于是  dp\[i\]\[j\] =

dp\[k\]\[i\] + 1  ；

ii.  a  存在，但是  b < a < c  ：此时只能两个元素⾃⼰玩了，  dp\[i\]\[j\] = 2  ；

iii.  a  不存在：此时依旧只能两个元素⾃⼰玩了，  dp\[i\]\[j\] = 2  。

综上，状态转移⽅程分情况讨论即可。

优化点：我们发现，在状态转移⽅程中，我们需要确定  a  元素的下标。因此我们可以在  dp  之

前，将所有的「元素 + 下标」绑定在⼀起，放到哈希表中。

3.  初始化：

可以将表⾥⾯的值都初始化为  2  。

4.  填表顺序：

a.  先固定最后⼀个数；

b.  然后枚举倒数第⼆个数。

5.  返回值：

因为不知道最终结果以谁为结尾，因此返回  dp  表中的最⼤值  ret  。

但是  ret  可能⼩于  3  ，⼩于  3  的话说明不存在。

因此需要判断⼀下。

### 解题代码： ###

class Solution {
    public:
        int lenLongestFibSubseq(vector<int>& arr) {
            int n=arr.size();
            unordered_map<int,int>hash;
            vector<vector<int>>dp(n,vector<int>(n,2));
            for(int i=0;i<n;i++)
                hash[arr[i]]=i;
            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]&&hash.count(a))
                    dp[i][j]=dp[hash[a]][i]+1;
                    ret=max(ret,dp[i][j]);
                }
            }
            return ret<3?0:ret;
        }
    };

[1218.]: https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/
[873.]: https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/
[e36c992b2c1b4cf096a5946f7a77b82a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/ee91a65856504149a9ecd5c8a9dc684d.png