最长的斐波那契子序列的长度
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 468 ms, 内存: 23.6 MB
import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;
/**
* Using Java Streams to solve the problem involves creating maps and performing the same dynamic programming logic
* but with stream operations. This approach showcases the use of modern Java features.
*/
public class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n = arr.length;
Map<Integer, Integer> index = new HashMap<>();
IntStream.range(0, n).forEach(i -> index.put(arr[i], i));
Map<Integer, Integer> longest = new HashMap<>();
int[] maxLen = {0};
IntStream.range(0, n).forEach(i ->
IntStream.range(i + 1, n).forEach(j -> {
int a = arr[i];
int b = arr[j];
int len = 2;
while (index.containsKey(a + b)) {
int c = a + b;
a = b;
b = c;
len++;
}
maxLen[0] = Math.max(maxLen[0], len);
})
);
return maxLen[0] >= 3 ? maxLen[0] : 0;
}
}解释
方法:
该题解采用了动态规划的方法。首先，利用哈希表maps存储数组中每个元素的索引，以便快速查找。dp[i][j]表示以arr[i]和arr[j]为最后两个元素的斐波那契子序列的最大长度。通过双层循环遍历所有可能的arr[i]和arr[j]组合，对每个组合，计算差值arr[i]-arr[j]，并检查该差值是否存在于数组中。如果存在，说明可以形成一个斐波那契子序列，dp表更新为dp[j][k]+1，k是差值对应的索引。循环中还使用一个变量res来维护全局的最长子序列长度。注意，为了避免无效计算，当arr[j]的两倍小于等于arr[i]时，内层循环会提前终止。
时间复杂度:
O(n^2)
空间复杂度:
O(n^2)
代码细节讲解
🦆
为什么在动态规划解法中，dp数组的初始化值是0？在更新dp[i][j]时，直接赋值dp[j][k]+1是否会导致错误的结果？
▷🦆
动态规划表中dp[i][j]为什么要取max(dp[j][k]+1, 3)而不是直接dp[j][k]+1？请解释这里为什么要确保最小长度为3。
▷🦆
在解法中提到当arr[j]*2 <= arr[i]就终止内循环，这个优化是基于什么逻辑或者数学原理？
▷