每日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;}
};