873. 最长的斐波那契子序列的长度

cucumber 发布于2019-08-16 13:37 / 355人阅读

摘要：示例输入输出解释最长的斐波那契式子序列有，以及。故我们使用二维数组来存储这一信息，二维数组的两个索引分别为该斐波那契数列前两个数在中的索引，其对应的值为由该数列在整个序列中的最大长度。

如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是斐波那契式的：

n >= 3
对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
给定一个严格递增的正整数数组形成序列，找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。

（回想一下，子序列是从原序列 A 中派生出来的，它从 A 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

示例 1：

输入: [1,2,3,4,5,6,7,8]
输出: 5
解释:
最长的斐波那契式子序列为：[1,2,3,5,8] 。
示例 2：

输入: [1,3,7,11,12,14,18]
输出: 3
解释:
最长的斐波那契式子序列有：
[1,11,12]，[3,11,14] 以及 [7,11,18] 。

如果直接使用遍历算法的话，时间复杂度大概是O(n^3)这个数量级，而题目要求中给出的数组A的最大长度为1000,如果使用O(n^3)的算法，势必会超时。
考虑如何简化：斐波那契数列有一个性质，即一但前两个数字确定，整个数列即确定的。故我们使用二维数组来存储这一信息，二维数组map的两个索引分别为该斐波那契数列前两个数在A中的索引，其对应的值为由该数列在整个序列中的最大长度。
我们只要从后往前遍历整个数组，就能使用到map中所储存的信息，具体代码如下：

代码：

class Solution {
    public int lenLongestFibSubseq(int[] A) {
        int res = 0;
        // HashMap map = new HashMap();
        int [][] map = new int [A.length][A.length];
        map[A.length- 2][A.length -1] = 2;
//        List  list = new ArrayList<>();
//        for(int i = 0 ; i < A.length ; i++){
//            list.add(A[i]);
//        }
        for(int j = A.length - 3; j >= 0; j--){
            for(int i = j + 1; i  target) {
                end = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }
}

云服务器 GPU云服务器波那契数列最长递增子序列最长公共子序列最长的域名

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72045.html

递归

摘要：递归概念递归是一种针对简单循环难以编程实现的问题，通过函数调用自身，提供优雅解决方案的技术。拥有基础情况或终止条件来停止递归。这个称之为递归调用。为了避免重新创建字符串，使用递归辅助方法来进行改良。递归概念递归是一种针对简单循环难以编程实现的问题，通过函数调用自身，提供优雅解决方案的技术。递归都具有以下三个要点：使用 if-else 或 switch 语句来引导不同的情况。 ...

alphahans 2019-08-20 12:14 评论0 收藏0
数据结构与算法:常见排序算法

摘要：这是一个简单的递归函数，你可以使用它来生成数列中指定序号的数值这个函数的问题在于它的执行效率非常低有太多值在递归调用中被重新计算。本章内容衔接上一章　数据结构与算法：二分查找内容提要两种基本数据结构：数组常见操作: 数组降维、数组去重链表递归：递归是很多算法都使用的一种编程方法　　- 如何将问题分成基线条件和递归条件　　- 分而治之策略解决棘手问题 ...

wuyumin 2019-07-30 15:33 评论0 收藏0
数据结构与算法:常见排序算法

摘要：这是一个简单的递归函数，你可以使用它来生成数列中指定序号的数值这个函数的问题在于它的执行效率非常低有太多值在递归调用中被重新计算。本章内容衔接上一章　数据结构与算法：二分查找内容提要两种基本数据结构：数组常见操作: 数组降维、数组去重链表递归：递归是很多算法都使用的一种编程方法　　- 如何将问题分成基线条件和递归条件　　- 分而治之策略解决棘手问题 ...

Carson 2019-08-26 11:32 评论0 收藏0
从斐波那契数列看递归和动态规划

摘要：大名鼎鼎的斐波那契数列，，，，，，，，使用数学归纳法可以看出其规律为。对于斐波那契数列的求解，有自顶向下的记忆化搜索递归和自下向上的迭代法，他们都使用了动态规划的思想。大名鼎鼎的斐波那契数列：0，1，1，2，3，5，8，13，21...使用数学归纳法可以看出其规律为：f(n) = f(n-1) + f(n-2)。递归下面首先直接使用递归（JavaScript实现）来求解第 n ...

charles_paul 2019-08-22 18:30 评论0 收藏0
js 实现斐波那契数列(数组缓存、动态规划、尾调用优化)

摘要：根据该规则，返回第个斐波那契数。尾递归函数调用自身，称为递归。一个前端眼中的斐波那契数列解斐波那契数列的实用解法调用栈尾递归和手动优化尾调用优化译我从用写斐波那契生成器中学到的令人惊讶的件事斐波那契数列是以下一系列数字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在种子数字 0 和 1 ...

赵连江 2019-08-23 11:38 评论0 收藏0