力扣 – 劍指 Offer 10- I. 斐波那契數列

• 2021 年 11 月 27 日
• 筆記
• 動態規劃, 演算法與題解, 遞歸

題目

劍指 Offer 10- I. 斐波那契數列

思路1（遞歸 / 自頂向下）

• 這題是很常見的一道入門遞歸題，可以採用自頂向下的遞歸方法，比如我們要求第n個位置的值，根據斐波那契數列的定義fib(n) = fib(n-1) + fib(n-2)，即等於前一個和前前一個兩個的值之和

• 但是如果直接遞歸，會導致很多重複的計算，效率很低，比如 n 為 5 時：

  1. fib(5) 為 fib(4) 和 fib(3) 兩個值之和

  2. 然後 fib(4) 又等於 fib(3) 和 fib(2) 兩個值之和。注意， fib(3) 在上一步已經求過了，這裡還要再求一次

  3. 另一個 fib(3) 即為 fib(2) 和 fib(1) 兩個值之和，同樣，fib(2)，也被求過了

  4. ……

     

• 根據上面例子我們可以發現這樣子會導致很多多餘的計算，做無用功，也會出現由於 n 的增大導致計算量急劇增大。因此我們可以將這個演算法優化一下，就是添加一個表格 memory 來記錄計算過的值，在每次遞歸的時候，判斷一下之前是否計算過了，如果發現計算過了，直接返回數組中對應的值，否則就計算一下，然後記錄到 memory 表格里

程式碼

class Solution {

    int[] memory;

    public int fib(int n) {
        memory = new int[n+1];
        return help(n);
    }

    public int help(int n) {
        // 遞歸結束的條件
        if (n <= 1) {
            return n;
        }

        // 判斷是否計算過了
        if (memory[n] != 0) {
            return memory[n];
        }

        // 沒有在 memory 中找到就計算一下，然後在記錄到 memory 中
        int i = help(n - 1) + help(n - 2);
        i %= 1000000007;
        memory[n] = i;

        return memory[n];
    }
}

複雜度分析

• 時間複雜度：\(O(N)\)
• 空間複雜度：\(O(N)\)

思路2（迭代 / 動態規格）

• 同樣，根據斐波那契數列定義，可以發現第 n 個的值為前兩個值之和，因此我們可以從第一個開始計算，循環計算到 n就得到了結果，空間上僅僅佔兩個變數的空間，為 \(O(1)\) ，程式碼如下：

程式碼

class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }

        int a = 1;
        int b = 1;

        for (int i = 2; i < n; i++) {
            int temp = (a + b);
            a = b;
            b = temp;
            b %= 1000000007;
        }

        return b;
    }
}

複雜度分析

• 時間複雜度：\(O(N)\)
• 空間複雜度：\(O(1)\)