題目描述
這是 LeetCode 上的 873. 最長的斐波那契子序列的長度 ,難度為 中等。
Tag : 「序列 DP」、「哈希表」、「動态規劃」
如果序列
-
n >= 3
- 對于所有
,都有i + 2 <= n
給定一個嚴格遞增的正整數數組形成序列
arr
,找到
arr
中最長的斐波那契式的子序列的長度。如果一個不存在,傳回
(回想一下,子序列是從原序列
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]
提示:
序列 DP
定義 為使用 為斐波那契數列的最後一位,使用 為倒數第二位(即
不失一般性考慮 該如何計算,首先根據斐波那契數列的定義,我們可以直接算得 前一位的值為 ,而快速得知 值的坐标 ,可以利用
arr
的嚴格單調遞增性質,使用「哈希表」對坐标進行轉存,若坐标 存在,并且符合 ,說明此時至少湊成了長度為 的斐波那契數列,同時結合狀态定義,可以使用 來更新 ,即有狀态轉移方程:
同時,當我們「從小到大」枚舉 ,并且「從大到小」枚舉
- 可行性剪枝:當出現,說明即使存在值為的下标,根據
單調遞增性質,也不滿足的要求,且繼續枚舉更小的,仍然有,仍不合法,直接arr
掉目前枚舉break
- 最優性剪枝:假設目前最大長度為
,隻有當,我們才有必要往下搜尋,的含義為以ans
代碼:
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
- 時間複雜度:存入哈希表複雜度為;
過程複雜度為。整體複雜度為DP
- 空間複雜度:
最後
這是我們「刷穿 LeetCode」系列文章的第
No.873
篇,系列開始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道題目,部分是有鎖題,我們将先把所有不帶鎖的題目刷完。
在這個系列文章裡面,除了講解解題思路以外,還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。