题目
873.
最长的斐波那契子序列的长度
如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式
的：
n >= 3- 对于所有
i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
给定一个严格递增的正整数数组形成序列 arr ，找到
arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0
。
（回想一下，子序列是从原序列
arr 中派生出来的，它从
arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）
示例 1：
输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。
示例 2：
输入: arr = [1,3,7,11,12,14,18]
输出: 3
解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18]
。
提示：
- \(3 <= arr.length <=
1000\)
- \(1 <= arr[i] < arr[i + 1] <=
10^9\)
标签
数组, 哈希表, 动态规划
相似题目
题解
【最长的斐波那契子序列的长度】动态规划
朴素动态规划
不难想到使用动态规划求解，定义数组 dp[i][j]
表示最后两个值是 arr[i], arr[j]
的最长严格递增斐波那契子序列，那么状态转移方程为
\[
dp[i][j] = dp[k][i] + 1, \text{if} \quad k < i \quad\&\quad
arr[k] + arr[i] = arr[j]
\]
朴素做法是直接枚举 \(K\)
求解，很遗憾虽然通过了全部测试用例但总时间超时了。
![超时了]()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n = arr.length, ans = 0;
if (n < 3) return 0;
int[][] dp = new int[n][n];
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
for (int k = 0; k < i && arr[i] + arr[k] <= arr[j]; ++k) {
if (arr[k] + arr[i] == arr[j]) dp[i][j] = Math.max(3, Math.max(dp[k][i] + 1, dp[i][j]));
}
ans = Math.max(ans, dp[i][j]);
}
}
return ans;
}
}
|
- 时间复杂度: \(O(n^3)\)
- 空间复杂度: \(O(n^2)\)
哈希优化的动态规划
注意到有三重循环，最内层的循环是查找一个满足 \(arr[k] + arr[i] = arr[j]\) 的 k
值，事实上由于数组严格单调递增，这样的 \(k\) 最多只有一个，所以我们可以借助哈希表 在
\(O(1)\) 时间内 确定 \(k\) 值。
PS：注意排除 \(k == i\)
的特殊情况(即 \(arr[i] + att[i] =
arr[j]\))
Python 用了记忆化搜索，但不知道为什么会超时......
超时的测试用例丢到控制台运行时间是 196 ms, 而 C++ 超过 94%
的运行时间都是 200 ms, 很迷惑... 将 cache 改为 lru_cache 通过了(3700
ms)...
已补充 Python 的动态规划(1880 ms)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n = arr.length, ans = 0;
Map<Integer, Integer> st = new HashMap<>();
for (int i = 0; i < n; ++i) st.put(arr[i], i);
if (n < 3) return 0;
int[][] dp = new int[n][n];
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
int target = arr[j] - arr[i];
if (target >= arr[i]) continue;
if (st.containsKey(target)) {
int k = st.get(target);
dp[i][j] = Math.max(3, dp[k][i] + 1);
ans = Math.max(ans, dp[i][j]);
}
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def lenLongestFibSubseq(self, arr: List[int]) -> int:
st = {j: i for i, j in enumerate(arr)}
n, ans = len(arr), 0
dp = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(i + 1, n):
target = arr[j] - arr[i]
if target < arr[i] and target in st:
dp[i][j] = max(3, dp[st[target]][i] + 1)
ans = max(ans, dp[i][j])
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def lenLongestFibSubseq(self, arr: List[int]) -> int:
st = {j: i for i, j in enumerate(arr)}
n = len(arr)
@cache
def dfs(i, j):
""" 最后两个值是 arr[i], arr[j] 的最长斐波那契数列长度 """
target = arr[j] - arr[i]
if target < arr[i] and target in st:
return max(3, dfs(st[target], i) + 1)
return 0
return max(dfs(i, j) for i in range(n) for j in range(i + 1, n))
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr) {
int n = arr.size(), ans = 0;
unordered_map<int, int> st;
for (int i = 0; i < n; ++i) st.emplace(arr[i], i);
if (n < 3) return 0;
vector<vector<int>> dp (n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
int target = arr[j] - arr[i];
if (target >= arr[i]) continue;
if (st.find(target) != st.end()) {
int k = st[target];
dp[i][j] = max(3, dp[k][i] + 1);
ans = max(ans, dp[i][j]);
}
}
}
return ans;
}
};
|
- 时间复杂度: \(O(n^2)\)
- 空间复杂度: \(O(n^2)\)
如果对你有帮助的话，请给我点个赞吧~
欢迎前往 我的博客
或 Algorithm -
Github 查看更多题解
/20220709104809.png)