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

个人主页：兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

点击直接跳转到该题目

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

最后就通过啦！！！