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

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

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

思路分析

解法一：动态规划（推荐）

核心思路：

用 dp[j][i] 表示以 arr[j]、arr[i] 结尾的斐波那契子序列长度。

若存在 k 使得 arr[k] + arr[j] = arr[i]，则 dp[j][i] = dp[k][j] + 1。

使用哈希表快速定位 k。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示数组长度。

空间复杂度：O(n^2)，存储 DP 表。

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        Map<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++) {
                int kVal = arr[i] - arr[j];
                Integer k = index.get(kVal);
                if (k != null && k < j) {
                    dp[j][i] = Math.max(dp[k][j] + 1, 3);
                    ans = Math.max(ans, dp[j][i]);
                }
            }
        }

        return ans;
    }
}

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

	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}

	ans := 0
	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			kVal := arr[i] - arr[j]
			k, ok := index[kVal]
			if ok && k < j {
				if dp[k][j] == 0 {
					dp[j][i] = 3
				} else {
					dp[j][i] = dp[k][j] + 1
				}
				if dp[j][i] > ans {
					ans = dp[j][i]
				}
			}
		}
	}

	return ans
}

相似题目

题目	难度	考察点
300. 最长递增子序列	中等	DP
873. 最长的斐波那契子序列的长度	中等	DP
1027. 最长等差数列	中等	DP
1218. 最长定差子序列	中等	DP
1137. 第 N 个泰波那契数	简单	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/92468024