网站开发国内外研究背景,网站管理登录系统,深圳东门老街美食攻略,策划方案范文目录
力扣873. 最长的斐波那契子序列的长度
解析代码 力扣873. 最长的斐波那契子序列的长度
873. 最长的斐波那契子序列的长度
难度 中等
如果序列 X_1, X_2, ..., X_n 满足下列条件#xff0c;就说它是 斐波那契式 的#xff1a;
n 3对于所有 i 2 n#x…目录
力扣873. 最长的斐波那契子序列的长度
解析代码 力扣873. 最长的斐波那契子序列的长度
873. 最长的斐波那契子序列的长度
难度 中等
如果序列 X_1, X_2, ..., X_n 满足下列条件就说它是 斐波那契式 的
n 3对于所有 i 2 n都有 X_i X_{i1} X_{i2}
给定一个严格递增的正整数数组形成序列 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(vectorint 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(vectorint arr) {int n arr.size(), ret 2;unordered_mapint, int hash(n);for(int i 0; i n; i){hash[arr[i]] i;}vectorvectorint dp(n, vectorint(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;}
};
