每日OJ题_子序列dp⑥_力扣873. 最长的斐波那契子序列的长度

目录

力扣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] 的一个子序列）

示例 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

class Solution {
public:int lenLongestFibSubseq(vector<int>& arr) {}
};

---

解析代码

动态规划解法思路：

状态表示：以某个位置为结尾，结合题目要求，先定义⼀个状态表示：

dp[i] 表示：以 i 位置元素为结尾的所有子序列中，最长的斐波那契子数列的长度。

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

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

dp[i][j] 表示：以 i 位置以及 j 位置的元素为结尾的所有的子序列中，最长的斐波那契子序列的长度。规定一下 i < j 。

状态转移方程：

设 nums[i] = b, nums[j] = c ，那么这个序列的前一个元素就是 a = c - b 。根据 a 的情况讨论：

• a 存在，下标为 k ，并且 a < b ：此时我们需要以 k 位置以及 i 位置元素为结尾的最长斐波那契子序列的长度，然后再加上 j 位置的元素（+1）即可。于是 dp[i][j] =dp[k][i] + 1 ;
• a 存在，但是 b < a < c ：此时只能有两个元素， dp[i][j] = 2 ;
• a 不存在：此时依旧只有两个元素， dp[i][j] = 2 ;

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

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

        初始化：可以将表里面的值都初始化为 2 。

        填表顺序：先固定斐波那契子序列的最后一个数，然后枚举倒数第二个数。

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

class Solution {
public:int lenLongestFibSubseq(vector<int>& arr) {int n = arr.size(), ret = 2;unordered_map<int, int> hash(n);for(int i = 0; i < n; ++i){hash[arr[i]] = i;}vector<vector<int>> dp(n, vector<int>(n, 2));// dp[i][j] 表示：以i位置及j位置的元素为结尾的子序列中，最长的斐波那契子序列的长度。i < j 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; // hash[a]就是a元素下标ret = max(ret, dp[i][j]); }}return ret < 3 ? 0 : ret;}
};