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

cucumber 發布于2019-08-16 13:37 / 431人閱讀

摘要：示例輸入輸出解釋最長的斐波那契式子序列有，以及。故我們使用二維數組來存儲這一信息，二維數組的兩個索引分別為該斐波那契數列前兩個數在中的索引，其對應的值為由該數列在整個序列中的最大長度。

如果序列 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云服務器波那契數列最長遞增子序列最長公共子序列最長的域名

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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