力扣题解(最长的斐波那契子序列的长度)
如果序列 X_1, X_2, ..., X_n
满足下列条件,就说它是 斐波那契式 的:
n >= 3
- 对于所有
i + 2 <= n
,都有X_i + X_{i+1} = X_{i+2}
给定一个严格递增的正整数数组形成序列 arr ,找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在,返回 0 。
(回想一下,子序列是从原序列 arr 中派生出来的,它从 arr 中删掉任意数量的元素(也可以不删),而不改变其余元素的顺序。例如, [3, 5, 8]
是 [3, 4, 5, 6, 7, 8]
的一个子序列)
思路:
首先,本题中要求i位置的斐波那契子序列,一定和(0-i-1)的元素有关,因为是在(0-i-1)中的某些元素加上i位置元素构成以i位置为最后一个元素的最长斐波那契子序列。但如果仅仅是一维的dp,此时只能知道(0-i-1)的dp的值,无法得知具体构成,此时无法确定(0-i-1)内的最长斐波那契子序列加上i位置的元素是否仍能构成斐波那契子序列。因此需要多维dp[i][j],表示前一个元素是i位置,后一个元素是j位置去构成斐波那契子序列,这时候在前面符合要求的元素的值就是arr[j]-arr[i],只有满足数值的才可能能构成斐波那契数列。此外,对于满足的数值,若其下标出现在i,j之间,则可以由dp[k][j]来表示(此时i出现在k前面),因此对于dp[i][j]忽略这种情况,以保证所满足的数值一定出现在i前面。当k出现在前面时,k位置构成的斐波那契数列加上i位置,j位置元素不受影响一定还是斐波那契数列,因此符合要求。dp[i][j]=1+dp[k][i]。
核心思路就是用多维表示。
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr) {
int n=arr.size();
vector<vector<int>>dp(n,vector<int>(n,2));
unordered_map<int,int>hash;
hash[arr[0]]=0;
for(int i=1;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
int a=arr[j]-arr[i];
if(hash.count(a)&&hash[a]<i)
{
dp[i][j]=max(dp[i][j],dp[hash[a]][i]+1 );
}
}
hash[arr[i]]=i;
}
int ret=0;
for(auto e:dp)
{
for(auto s:e)
ret=max(ret,s);
}
return ret>2?ret:0;
}
};
原文地址:https://blog.csdn.net/yyssas/article/details/140380161
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!