題目描述

斐波那契數(shù)，通常用 F(n) 表示，形成的序列稱為斐波那契數(shù)列。
該數(shù)列由 0 和 1 開始，后面的每一項(xiàng)數(shù)字都是前面兩項(xiàng)數(shù)字的和。
也就是：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
給定 N，計(jì)算 F(N)。

示例 1：
輸入：2
輸出：1
解釋：F(2) = F(1) + F(0) = 1 + 0 = 1.

示例 2：
輸入：3
輸出：2
解釋：F(3) = F(2) + F(1) = 1 + 1 = 2.

示例 3：
輸入：4
輸出：3
解釋：F(4) = F(3) + F(2) = 2 + 1 = 3.

提示：
0 ≤ N ≤ 30

算法思維

• 遞歸、動(dòng)態(tài)規(guī)劃

解題要點(diǎn)

• 使用動(dòng)態(tài)規(guī)劃的思想減少重復(fù)計(jì)算和函數(shù)的重復(fù)調(diào)用

解題思路

一. Comprehend 理解題意

• 每個(gè)數(shù)字由其前面兩個(gè)數(shù)字計(jì)算得到
• 因此得到目標(biāo)結(jié)果的必要條件是已知此前兩數(shù)
  
  

二. Choose 選擇數(shù)據(jù)結(jié)構(gòu)與算法

遞歸解法

• 數(shù)據(jù)結(jié)構(gòu)：-
• 算法思維：遞歸
  
  

三. Code 編碼實(shí)現(xiàn)基本解法

class Solution {
    public int fib(int N) {
        //1.遞歸結(jié)束條件
            if (N <= 1) {
                return N;
            }

            //2.主體邏輯

            //3.遞歸公式：F(n) = F(n-1) + F(n-2)
            return fib(N - 1) + fib(N - 2);
        
    }
}

執(zhí)行耗時(shí)：8 ms，擊敗了 29.92% 的Java用戶
內(nèi)存消耗：35.5 MB，擊敗了 5.16% 的Java用戶

時(shí)間復(fù)雜度：O(2ⁿ)
? ? n 層遞歸調(diào)用，每層分支成兩個(gè)新的遞歸
? ? 可以看成一個(gè)二叉樹，樹的節(jié)點(diǎn)數(shù)即為函數(shù)的調(diào)用次數(shù)
? ? 調(diào)用次數(shù)為 2ⁿ-1 次

空間復(fù)雜度：O(n)
? ? 遞歸運(yùn)算的空間復(fù)雜度 = 遞歸深度

四. Consider 思考更優(yōu)解

改變算法思維

• 使用動(dòng)態(tài)規(guī)劃的思維減少函數(shù)的重復(fù)調(diào)用
  
  

五. Code 編碼實(shí)現(xiàn)最優(yōu)解

優(yōu)化解法：動(dòng)態(tài)規(guī)劃解法

class Solution {
 //簡(jiǎn)化版動(dòng)態(tài)規(guī)劃，臨時(shí)變量只存放最近兩個(gè)
    public int fib3(int N) {
        int pre_2 = 0, pre_1 = 0, current = 1;
        for (int i = 1; i <= N; i++) {
            pre_2 = pre_1;
            pre_1 = current;
            current = pre_1 + pre_2;
        }
        return current;
    }
}

執(zhí)行耗時(shí)：0 ms，擊敗了 100.00% 的Java用戶
內(nèi)存消耗：35.3 MB，擊敗了 16.74% 的Java用戶

時(shí)間復(fù)雜度：O(n)
? ? n 次遍歷

空間復(fù)雜度：O(1)
? ? 三個(gè)用于記錄數(shù)值的局部變量

六. Change 變形與延伸

=== 待續(xù) ===