題目描述
這是 LeetCode 上的 873. 最長的斐波那契子序列的長度 摇锋，難度為 中等丹拯。
Tag : 「序列 DP」、「哈希表」荸恕、「動(dòng)態(tài)規(guī)劃」
如果序列 滿足下列條件乖酬，就說它是 斐波那契式 的：
n >= 3- 對于所有
i + 2 <= n，都有
給定一個(gè)嚴(yán)格遞增的正整數(shù)數(shù)組形成序列 arr融求，找到 arr 中最長的斐波那契式的子序列的長度咬像。如果一個(gè)不存在，返回 生宛。
（回想一下县昂，子序列是從原序列 arr 中派生出來的，它從 arr 中刪掉任意數(shù)量的元素（也可以不刪）陷舅，而不改變其余元素的順序倒彰。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一個(gè)子序列）
示例 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] 。
提示：
序列 DP
定義 為使用
為斐波那契數(shù)列的最后一位仰剿，使用
為倒數(shù)第二位（即
的前一位）時(shí)的最長數(shù)列長度创淡。
不失一般性考慮 該如何計(jì)算，首先根據(jù)斐波那契數(shù)列的定義南吮，我們可以直接算得
前一位的值為
琳彩，而快速得知
值的坐標(biāo)
，可以利用
arr 的嚴(yán)格單調(diào)遞增性質(zhì)旨袒，使用「哈希表」對坐標(biāo)進(jìn)行轉(zhuǎn)存汁针，若坐標(biāo) 存在，并且符合
砚尽，說明此時(shí)至少湊成了長度為
的斐波那契數(shù)列施无，同時(shí)結(jié)合狀態(tài)定義，可以使用
來更新
必孤，即有狀態(tài)轉(zhuǎn)移方程：
同時(shí)猾骡，當(dāng)我們「從小到大」枚舉 瑞躺，并且「從大到小」枚舉
時(shí)，我們可以進(jìn)行如下的剪枝操作：
- 可行性剪枝：當(dāng)出現(xiàn)
兴想，說明即使存在值為
的下標(biāo)
幢哨，根據(jù)
arr單調(diào)遞增性質(zhì)，也不滿足的要求嫂便，且繼續(xù)枚舉更小的
捞镰，仍然有
break掉當(dāng)前枚舉 - 最優(yōu)性剪枝：假設(shè)當(dāng)前最大長度為
ans，只有當(dāng)厂画，我們才有必要往下搜索凸丸，
的含義為以
為斐波那契數(shù)列倒數(shù)第二個(gè)數(shù)時(shí)的理論最大長度。
代碼：
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n = arr.length, ans = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) map.put(arr[i], i);
int[][] f = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = i - 1; j >= 0 && j + 2 > ans; j--) {
if (arr[i] - arr[j] >= arr[j]) break;
int t = map.getOrDefault(arr[i] - arr[j], -1);
if (t == -1) continue;
f[i][j] = Math.max(3, f[j][t] + 1);
ans = Math.max(ans, f[i][j]);
}
}
return ans;
}
}
- 時(shí)間復(fù)雜度：存入哈希表復(fù)雜度為
袱院；
DP過程復(fù)雜度為屎慢。整體復(fù)雜度為
- 空間復(fù)雜度：
最后
這是我們「刷穿 LeetCode」系列文章的第 No.873 篇，系列開始于 2021/01/01忽洛，截止于起始日 LeetCode 上共有 1916 道題目腻惠，部分是有鎖題，我們將先把所有不帶鎖的題目刷完脐瑰。
在這個(gè)系列文章里面妖枚，除了講解解題思路以外，還會(huì)盡可能給出最為簡潔的代碼苍在。如果涉及通解還會(huì)相應(yīng)的代碼模板绝页。
為了方便各位同學(xué)能夠電腦上進(jìn)行調(diào)試和提交代碼，我建立了相關(guān)的倉庫：https://github.com/SharingSource/LogicStack-LeetCode 寂恬。
在倉庫地址里续誉，你可以看到系列文章的題解鏈接、系列文章的相應(yīng)代碼初肉、LeetCode 原題鏈接和其他優(yōu)選題解酷鸦。
更多更全更熱門的「筆試/面試」相關(guān)資料可訪問排版精美的 合集新基地 ????
本文由mdnice多平臺發(fā)布
