873. 最长的斐波那契子序列的长度
https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/
经典的dp题目,解题时主要遇到的问题在于不会定义dp数组（dp table）以及下标的含义,上来就想着定义一维的dp数组,但是问题很明显是行不通的,初始想法是对于不断遍历到的新的数字,在已有的数字中寻找是否有加和正好是的组合,但是明显是会超时的.
使用二维数组的思路如下:dp[i][j]代表以arr[i]结尾,arr[j]为倒数第二个字母的最长数列长度,那么问题就转变为由斐波那契数列的定义,寻找前一个数字的问题,对于如何寻找,可以采用HashMap的形式,定义一个HashMap来快速寻找.即,将值为arr[i]的元素的值作为key,将数值arr[i]作为value.同时对于状态转移方程,定义如下,如果在前面找到了满足的解,那么很显然,解的最短长度至少为3,即Math.max(3,dp[j][t]),(回想dp[i][j]的定义,dp[j][t]正好是以arr[j]结尾,arr[t]为倒数第二个的数列),同时遍历顺序确定如下,对于外层循环,肯定是从前到后依次遍历,对于内层循环,则采用从后到前的顺序遍历.为什么内层循环采用从后往前的顺序呢–为了优化搜索空间.
优化方式1:
若arr[i]-arr[j]的值小于arr[j],那么由于数列是递增的,说明即使存在值为 arr[i] – arr[j] 的下标 t，根据 arr 单调递增性质，也不满足 t < j < i 的要求(三个数字要依次递增)，且继续枚举更小的 j，仍然有 arr[i] – arr[j] >= arr[j]，所以直接break当前循环.
优化方式2:
若j+2<ans,则没有必要继续向前推进,即当前的最长长度已经大于前一个j为结尾的最长长度+2,所以没有必要再向前计算,这种计算是无法增加ans的值的,就是说前面的长度不够.
代码如下:
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n = arr.length;
int ans = 0;
int dp[][] = new int [n][n];
Map <Integer, Integer> map = new HashMap<>();
for (int i = 0; i<n;i++ ) map.put(arr[i],i);
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 order = map.getOrDefault(arr[i] - arr[j],-1);
if (order == -1){
continue;
}else{
dp[i][j] = Math.max(3,dp[j][order]+1);
ans = Math.max(dp[i][j], ans);
}
}
}
return ans;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/88897.html
