辽阳做网站的公司,西宁网站制作哪里好,网站开发语言版本不同,生道网站建设平台目录
最长的斐波那契数列子序列的长度
1.题目
2.题目接口
3.解题思路及其代码 最长的斐波那契数列子序列的长度
1.题目 如果序列x_1#xff0c;X_2#xff0c;...#xff0c;x_n 满足下列条件#xff0c;就说它是斐波那契式的: 1.n 3 2.对于所有i2 nX_2...x_n 满足下列条件就说它是斐波那契式的: 1.n 3 2.对于所有i2 n都有 x_i X_{i1} X_{i2} 给定一个严格递增的正整数数组形成序列arr找到arr中最长的斐波那契式的子序列的长度。如果一个不存在返回0。 (回想一下子序列是从原序列arr中派生出来的它从arr中删掉任意数量的元素(也可以不删)而不改变其余元素的顺序。例如[358] 是[3 45678]的一个子序列) 示例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] 。 提示: arr.length 1000 1 arr[ilarr[i 1] 10^9 2.题目接口
class Solution {
public:int lenLongestFibSubseq(vectorint arr) {}
};
3.解题思路及其代码 这道题我们还是用动态规划的思想来解决。解决步骤如下 1.状态转移方程 状态转移方程的定义还是以老套路以dp[i]位置为结尾表示以i位置为结尾的最长的斐波那契数列。但是我们在这道题里面该用什么表示这个状态转移方程呢我的解决方法是用二维数组的方式。以dp[i][j]表示以arr[i]和arr[j]为结尾的的子序列的最长长度。那我们的dp[i][j]又该如何推导呢dp[i][j] dp[k][i]1dp[k][i]表示以arr[k]和arr[i]为结尾的最长的斐波那契数列加1表示当arr[j]与能作为斐波那契数列的一份子时加上arr[j]这个位置。 2.初始化 因为斐波那契数列的长度至少为3。所以我们在初始化dp表时可以先初始化为2.如下 int n arr.size();
vectorvectorintdp(n,vectorint(n,2)); 然后在返回时做如下判断 return Maxlenth 2?0:Maxlenth; 便可以返回最终的正确结果。 3.优化 这道题如果不进行优化处理那这道题的时间复杂度将会达到n^3。因为填表时要利用三层循环。但是如果进行如下优化利用unordered_map将数组元素和下标进行绑定。 unordered_mapint,inthash;for(int i 0;in;i)
{hash[arr[i]] i;//下标和数组的值进行绑定
} 便可以将时间复杂度降到n^2。 解题代码如下 class Solution {
public:int lenLongestFibSubseq(vectorint arr) {int n arr.size();vectorvectorintdp(n,vectorint(n,2));unordered_mapint,inthash;for(int i 0;in;i){hash[arr[i]] i;//下标和数组的值进行绑定}int Maxlenth 2;for(int j 2;jn;j){for(int i 1;in;i){int num arr[j] - arr[i];//前面的数的大小if(hash.count(num)hash[num]i)//这里的顺序不能变{dp[i][j] dp[hash[num]][i]1;}Maxlenth max(Maxlenth,dp[i][j]);}}return Maxlenth 2?0:Maxlenth;}
};
