LeetCode_873_LengthofLongestFibonacciSubsequence
題目分析：
本質(zhì)還是LIS，只是不能二分優(yōu)化了败玉。回憶這三個(gè)題走來沽损。
1.求上升。
2.上升條件變了畔塔。
3.不是上升了魏铅。--- 雖然結(jié)果數(shù)字是上升，但是之前維護(hù)的那個(gè)數(shù)組已經(jīng)無效了监婶。
dp[i][j] (i < j) 代表包含i和j下標(biāo)的子序列最大長(zhǎng)度。
倒著遍歷齿桃，如果A[i] + A[j]存在惑惶，長(zhǎng)度 + 1，否則長(zhǎng)度默認(rèn)是2短纵；
用一個(gè)max收集最大長(zhǎng)度带污。
if(map.containsKey(A[i] + A[j])){
int position = map.get(A[i] + A[j]);
dp[i][j] = dp[j][position] + 1;
}else {
dp[i][j] = 2;
}
計(jì)算過程中我們需要反復(fù)查詢某個(gè)“值”是否在數(shù)組中，數(shù)組只能根據(jù)下標(biāo)快速查詢香到。
所以我們用一個(gè)map鱼冀，來把只能下標(biāo)查詢的數(shù)組，變成可以值查詢的map悠就。
一點(diǎn)點(diǎn)數(shù)據(jù)結(jié)構(gòu)的感覺千绪？蛤？數(shù)據(jù)結(jié)構(gòu)本質(zhì)就是方便特定情況的CRUD梗脾。
解法一：直接dp
public static int lenLongestFibSubseq(int[] A) {
int max = 0;
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < A.length; i++)
map.put(A[i], i);
int [][]dp = new int[A.length][A.length];
for(int i = A.length - 1; i >= 0; i--){
for(int j = i + 1; j < A.length; j++){
if(map.containsKey(A[i] + A[j])){
int position = map.get(A[i] + A[j]);
dp[i][j] = dp[j][position] + 1;
max = Math.max(max,dp[i][j]);
}else {
dp[i][j] = 2;
}
}
}
return max;
}
解法二：暴力
/**
* 直接暴力效率也不差
*/
public static int lenLongestFibSubseq(int[] A) {
int max = 0;
Set<Integer> set = new HashSet<>();
for (int a : A)
set.add(a);
for (int i = 0; i < A.length; ++i)
for (int j = i + 1; j < A.length; ++j) {
int x = A[j], y = A[i] + A[j];
int length = 2;
while (set.contains(y)) {
int z = x + y;
x = y;
y = z;
max = Math.max(max, ++length);
}
}
return max >= 3 ? max : 0;
}