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

约 5 分钟
文章信息 5 个分类 4 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 哈希表 动态规划 LCR

题目描述

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

image-20260929004231393

image-20260929004231394

题意分析

在严格递增的正整数数组中选择一个子序列，要求长度至少为三，且从第三项开始，每项都等于前两项之和。元素可以不连续，但下标顺序必须保留；不存在这样的子序列时返回零。

只知道末尾一项不足以确定下一项，还必须知道倒数第二项。因此用最后两个下标描述状态。数组严格递增、没有重复值，又使这两个末尾值对应的前一项至多只有一个。

解法：末尾两项定义 DP

核心思路

[!blue]

定义 dp[j][i] 为以 arr[j]、arr[i] 作为最后两项的最长链长度，其中 j < i。任意两项都可以作为待扩展的起点，所以这些状态初始为 2，但两项本身还不算题目要求的答案。

若当前链还能向前接一项，它的值必须是 delta = arr[i] - arr[j]。用“值到下标”的哈希表找到对应下标 k；只有 k < j，三项才按原数组顺序排列，并且没有复用元素。

当前驱存在且顺序合法时，任何以这两项结尾的链都必须从 (k, j) 延伸，因此 dp[j][i] = dp[k][j] + 1。不存在合法前驱时就保留长度二。这里用减法是为了直接确定前驱值，无需逐个枚举第三个下标。

外层按末项下标 i 递增，计算 (j, i) 时，被依赖的 (k, j) 已在更早的外层轮次完成。只在成功连接前驱时更新答案，保证参与答案的长度至少为三；答案初始为零，无解时自然保持零。

解题步骤

  1. 建立值到下标的哈希表，并把所有 j < i 的 dp[j][i] 初始化为 2。
  2. 按 i 从小到大枚举最后一项，再枚举前一项 j < i。
  3. 查找 arr[i] - arr[j]。若得到的下标满足 k < j，用 dp[k][j] + 1 更新当前状态和答案。
  4. 返回答案。Java 先判断键是否存在；Go 保存的是下标加一，查不到时减一得到 -1，因此还要检查 k >= 0。

代码实现

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        // 数组严格递增无重复，值到下标是单射。
        Map<Integer, Integer> mp = new HashMap<>();

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

        // dp[j][i]：以 arr[j]、arr[i] 结尾的最长斐波那契式子序列长度，基准为 2。
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                dp[j][i] = 2;
            }
        }

        int answer = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int delta = arr[i] - arr[j];

                if (mp.containsKey(delta)) {
                    int k = mp.get(delta);

                    // k < j 必须严格：k == j 会复用同一元素，k > j 则顺序颠倒。
                    if (k < j) {
                        dp[j][i] = dp[k][j] + 1;
                        answer = Math.max(answer, dp[j][i]);
                    }
                }
            }
        }

        // 只有转移成功才更新答案，因此无解时自然返回 0。
        return answer;
    }
}

func lenLongestFibSubseq(arr []int) int {
    n := len(arr)
    // 存下标加一，查不到时零值 0 减一得 -1，与非法下标统一处理。
    mp := make(map[int]int, n)
    for i, v := range arr {
        mp[v] = i + 1
    }
    // dp[j][i]：以 arr[j]、arr[i] 结尾的最长斐波那契式子序列长度，基准为 2。
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
        for j := 0; j < i; j++ {
            dp[j][i] = 2
        }
    }
    answer := 0
    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            // 用减法回溯倒数第三项。
            delta := arr[i] - arr[j]
            k := mp[delta] - 1
            // k >= 0 表示存在，k < j 保证下标严格递增。
            if k >= 0 && k < j {
                dp[j][i] = dp[k][j] + 1
                answer = max(answer, dp[j][i])
            }
        }
    }
    return answer
}

复杂度分析

  • 时间复杂度：期望 $O(n^2)$，枚举所有末尾下标对，每对做常数次哈希查询与转移。
  • 空间复杂度：$O(n^2)$，保存成对状态，哈希表另占 $O(n)$。前驱状态分布在不同列，不能直接按相邻两行滚动。

关键点总结

[!green]

  • 最后两项决定唯一的前驱值，严格递增保证该值最多对应一个下标。
  • 只有 k < j < i 才是合法的子序列延伸，找到数值还不够。
  • 长度二是递推基准，长度至少三才计入答案。
  • 按最后一个下标递增计算，保证依赖的短链已经得到结果。

易错点总结

[!yellow]

  • 状态必须包含最后两个下标，因为下一项由最后两个值共同决定。
  • 找到倒数第三项后还要检查下标 k<j，防止复用元素或破坏原顺序。
  • 两元素状态长度为 2，但答案只有形成至少三项时才更新，无合法链返回 0。

相似题目

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