# \[873]\[中等]\[动态规划] 最长的斐波那契子序列的长度

## 题目描述

[873. 最长的斐波那契子序列的长度](https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence/)

如果序列 X\_1, X\_2, ..., X\_n 满足下列条件，就说它是 斐波那契式 的：

n >= 3 对于所有 i + 2 <= n，都有 X*i + X*{i+1} = X\_{i+2} 给定一个严格递增的正整数数组形成序列，找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。

（回想一下，子序列是从原序列 A 中派生出来的，它从 A 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， \[3, 5, 8] 是 \[3, 4, 5, 6, 7, 8] 的一个子序列）

示例 1：

```
输入: [1,2,3,4,5,6,7,8]
输出: 5
解释:
最长的斐波那契式子序列为：[1,2,3,5,8] 。
```

示例 2：

```
输入: [1,3,7,11,12,14,18]
输出: 3
解释:
最长的斐波那契式子序列有：
[1,11,12]，[3,11,14] 以及 [7,11,18] 。
```

提示：

* 3 <= A.length <= 1000
* 1 <= A\[0] < A\[1] < ... < A\[A.length - 1] <= 10^9
* （对于以 Java，C，C++，以及 C# 的提交，时间限制被减少了 50%）

## 解题思路

### 动态规划

这是一种特殊的LIS([\[300\]\[中等\]\[贪心\]\[二分\]\[动态规划\]\[树状数组\] 最长上升子序列](/garnet/suan-fa/xian-duan-shu/300-zui-chang-shang-sheng-zi-xu-lie.md))问题. 除了要求递增, 还要求递增的规律符合斐波那契式.

结合[\[300\]\[中等\]\[贪心\]\[二分\]\[动态规划\]\[树状数组\] 最长上升子序列](/garnet/suan-fa/xian-duan-shu/300-zui-chang-shang-sheng-zi-xu-lie.md)中的动态规划方法. 本题中, 当前数字是否与其之前某两个数构成斐波那契式, 需要记录两个数字. 因此状态数组应当是**二维的**.

例如, 对于斐波那契式的子序列 `A[1] = 2, A[2] = 3, A[4] = 5, A[7] = 8, A[10] = 13`, 结点之间的路径为 `(1, 2) <-> (2, 4) <-> (4, 7) <-> (7, 10)`. 我们将**两个连续项** `A[i]`, `A[j]`记为一个点`(i, j)`, 则当`A[i] + A[j] == A[k]`时, `(i, j)`节点和`(j, k)`是连通的.

定义二维状态数组为`dp`, `dp[i][j]`代表`(i, j)`这个节点, 或者换个说法, 以`A[i]`, `A[j]`为序列结尾的符合斐波那契式最长序列的长度, 则有`dp[j][k] = dp[i][j] + 1`.

300题动态规划的解法改造为:

```python
class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        index_map = {a: i for i, a in enumerate(A)}
        dp = [[2] * n for _ in range(n)]
        max_len = 0

        for k in range(n):
            for j in range(k):
                diff = A[k] - A[j]
                i = index_map.get(diff, None)
                if i is not None and i < j:
                    dp[j][k] = dp[i][j] + 1
                    max_len = max(max_len, dp[j][k])
        return max_len
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/873-zui-chang-de-fei-bo-na-qi-zi-xu-lie-de-chang-du.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.