【算法|动态规划No.24】leetcode LCR 093. 最长的斐波那契子序列的长度

- 日理万妓 2024-04-27 06:42 42阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞? 收藏✨ 留言✉ 加关注?本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[手撕算法系列专栏][Link 2]】【[LeetCode][]】  
> ?本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> ?希望我们一起努力、成长，共同进步。  
> ![在这里插入图片描述][530b2fdc59bf45d5bfa43fd373793841.png]

[点击直接跳转到该题目][Link 3]

#### 目录 ####

*  1️⃣题目描述
 *  2️⃣题目解析
 *  3️⃣解题代码

## 1️⃣题目描述 ##

如果序列 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\] 的一个子序列）

## 2️⃣题目解析 ##

**状态表示：**

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

**状态转移方程：**

*  `如果(arr[j] - arr[i])存在并且(arr[j] - arr[i]) < arr[i]的话`：`dp[i][j] = dp[i][j] = dp[hash[a]][i] + 1`
 *  其它情况`dp[i][j]均为2`.

## 3️⃣解题代码 ##

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

**最后就通过啦！！！**

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[LeetCode]: https://blog.csdn.net/m0_74352571/category_12252087.html
[530b2fdc59bf45d5bfa43fd373793841.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/97008ae0f7744219ae4bffc0fcc020c9.png
[Link 3]: https://leetcode.cn/problems/Q91FMA/description/