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

2023-12-21 17:41:22

跳转汇总链接

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


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

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


文章来源:https://blog.csdn.net/m0_67470729/article/details/135118641
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。