LeetCode 873. 最长的斐波那契子序列的长度

约 5 分钟
文章信息 9 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 阿里 美团 旷视
标签
数组 哈希表 动态规划

题目描述

✅ 873. 最长的斐波那契子序列的长度

image-20260929000454582

image-20260929000454583

题意分析

从严格递增的正整数数组中选出最长子序列，使从第三项开始，每项都等于前两项之和。可以跳过元素，但不能改变下标顺序；长度至少为 3 才合法，不存在时返回 0。

解法：两数结尾动态规划

核心思路

[!blue]

下一项由前两项共同决定，只记录最后一个位置不足以判断能否延长。因此定义 dp[j][i] 为以 arr[j]、arr[i] 作为最后两项的最长长度，其中 j < i。任意两项都能作为起点，先把状态设为 2，但它还不是合法答案。

若这两项之前还有一项，它只能是 arr[i] - arr[j]。数组严格递增，每个值只有一个下标，可用哈希表直接找到候选位置 k。只有 k < j，才能把 arr[i] 接到以 k、j 结尾的子序列后，得到 dp[j][i] = dp[k][j] + 1；否则状态保持为 2。

前驱唯一，因此不需要枚举第三个下标或比较多个转移。按最后位置 i 递增计算，依赖的 dp[k][j] 已经完成；只在成功延长时更新答案，便能保证无解时仍返回 0。

解题步骤

  1. 建立 index[value] = 下标，创建二维状态数组，答案 ans 初始化为 0。
  2. 依次枚举最后位置 i，再枚举 0 <= j < i，令 dp[j][i] = 2。
  3. 查询 prev = arr[i] - arr[j] 的下标 k；存在且 k < j 时，令 dp[j][i] = dp[k][j] + 1 并更新 ans。
  4. 所有下标对处理完后返回 ans。

代码实现

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        HashMap<Integer, Integer> index = new HashMap<>();

        for (int i = 0; i < n; i++) {
            index.put(arr[i], i);
        }

        int[][] dp = new int[n][n];
        int ans = 0;

        for (int i = 0; i < n; i++) {
            // 外层结尾位置递增，所需更早结尾的状态已经完成
            for (int j = 0; j < i; j++) {
                // 两项只作为递推基线，合法答案至少包含三项
                dp[j][i] = 2;
                int prev = arr[i] - arr[j];
                Integer k = index.get(prev);

                // 命中值还需保证前驱下标更早，不能重复使用当前项
                if (k != null && k < j) {
                    dp[j][i] = dp[k][j] + 1;
                    ans = Math.max(ans, dp[j][i]);
                }
            }
        }

        return ans;
    }
}

func lenLongestFibSubseq(arr []int) int {
    n := len(arr)
    index := make(map[int]int)
    for i, num := range arr {
        index[num] = i
    }

    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
    }
    ans := 0
    for i := 0; i < n; i++ {
        // 外层结尾位置递增，所需更早结尾的状态已经完成
        for j := 0; j < i; j++ {
            // 两项只作为递推基线，合法答案至少包含三项
            dp[j][i] = 2
            prev := arr[i] - arr[j]
            // 命中值还需保证前驱下标更早，不能重复使用当前项
            if k, ok := index[prev]; ok && k < j {
                dp[j][i] = dp[k][j] + 1
                if dp[j][i] > ans {
                    ans = dp[j][i]
                }
            }
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：期望 $O(n^2)$，其中 n 是数组长度；每个下标对做一次哈希查询。
  • 空间复杂度：$O(n^2)$，二维状态占主要空间，索引表另需 $O(n)$。

关键点总结

[!green]

  • 用最后两项定义状态，才能确定唯一的前驱值。
  • 严格递增保证值与下标一一对应，但查到前驱后仍要检查 k < j。
  • 长度 2 用于开始递推，只有延长到至少 3 才更新答案。

易错点总结

[!yellow]

  • 只检查前驱值存在，可能复用 j 位置或选到它后面的元素，破坏子序列顺序。
  • 从默认值 0 开始转移会低估长度，每个二元状态都要先设为 2。
  • 把长度 2 计入答案，会在没有合法子序列时错误返回 2。
  • 枚举顺序必须保证最后位置更早的状态先完成，不能在 dp[k][j] 尚未计算时读取它。

相似题目

题目 难度 关联与区别
300. 最长递增子序列 中等 同样选取保持下标顺序的最长子序列，本题下一项由前两项之和确定，需要成对状态。
1027. 最长等差数列 中等 同样以最后两个元素或差值确定可延续条件，原题保持固定差，本题满足斐波那契加法关系。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/92468024
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！