【算法】【动规】最长斐波那契子序列的长度

跳转汇总链接

👉🔗动态规划算法汇总链接

2.6 最长的斐波那契子序列的长度

🔗题目链接

如果序列 X_1, X_2, …, X_n 满足下列条件，就说它是 斐波那契式 的：

n >= 3
对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。
如果一个不存在，返回 0 。

1. 状态表示
   • 考虑到两个连续数字才能推导出这一组斐波那契数，又需要我们以 “一个位置为自序列的结尾” 这样的方法去定义状态表示，于是考虑用如下定义：
   • dp[i][j] 表示，以 i 位置（前）以及 j 位置（后）的元素为结尾的所有子序列中，最长的斐波那契子序列的长度
2. 状态转移方程

   • 首先我们需要填写的是 dp[i][j]

   • 其次已知的值是 arr[i] 和 arr[j] 作为斐波那契子序列的结尾

   • 设倒数第三个数位置为 k 元素为 a，arr[i] 为 b，arr[j] 为 c，可以分为 a = c - b 是否存在，这两种大情况

     a 存在，且 a < b，dp[i][j] = dp[k][i] + 1;
     a 存在，但 b < a < c，dp[i][j] = 2;
     a 不存在，dp[i][j] = 2;
     

   • 式子应该很好理解，但是 k 的位置，也就是 a 的下标，却是不好确定的

   • 考虑在不在问题，同时题目表明 arr 是严格递增的，我们可以对状态转移方程做一个提前优化

3. 优化
   • 将 <arr 数组的元素，元素下标> ，作为 <key, value> 绑定，存在哈希表中。
4. 初始化
   • dp[][] 里都初始化为 2。
5. 填表顺序
   • 下标从小到大依次填写。
6. 返回值
   • dp表里的最大值，如果是 2 的话返回 0。

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        int retMax = 0;
        // 优化
        unordered_map<int, int> pos;
        for(int i = 0; i < n; i++) pos[arr[i]] = i;

        vector<vector<int>> dp(n, vector(n, 2));
        for (int j = 2; j < n; j++)     // 最后一个数
        {
            for(int i = 1; i < j; i++)  // 倒数第二个数
            {
                int a = arr[j] - arr[i];
                if(pos.count(a) && pos[a] < pos[arr[i]]) // 如果a存在，且位置正确
                {
                    dp[i][j] = dp[pos[a]][i] + 1;
                }
                retMax = max(retMax, dp[i][j]);
            }
            cout <<endl;
        }
        return retMax == 2 ? 0 : retMax;
    }
};

🥰如果本文对你有些帮助，欢迎👉 点赞 收藏 关注，你的支持是对作者大大莫大的鼓励！！(????) 若有差错恳请留言指正~~