費波那契數列解法總整理

這題是第一次學遞迴必出現的簡單例子，Fibonacci 數列，這個數列很有美感，這邊整理了三種解法，每種解法都帶出不同方向的概念，有趣！

一、Climbing Stairs 問題 (Fibonacci 數列)

Leetcode OJ - Climbing Stairs : https://leetcode.com/problems/climbing-stairs/

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

二、費波那契 與 費波那契數列

Fibonacci 為1200年代的歐洲數學家，在他的著作中曾經提到：「若有一隻免子每個月生一隻小免子，一個月後小免子也開始生產。起初只有一隻免子，一個月後就有兩隻免子，二個月後有三隻免子，三個月後有五隻免子（小免子投入生產）......」。

在數學上，費波那契數列是以遞迴的方法來定義：

$F_0=0$
$F_1=1$
$F_n = F_{n-1}+ F_{n-2}（n≧2）$

由0和1開始，之後的費波那契係數就由之前的兩數相加。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 (0不是第一項，而是第零項。)

三、費波那契數列問題詳解

1. Top-down Divide and Conquer Approach

直接把數學定義寫成程式碼，非常直覺；缺點是大量重複計算，因為每次 Fib(n) 重複使用時都要把整個遞迴樹展開。

Time Complexity : $O(2^n)$

class Solution {
public:
    int climbStairs(int n) {
        if (n==0) return 1;
        else if (n==1) return 1;
        else return climbStairs(n-1) + climbStairs(n-2);
    }
};

[用心去感覺] Divide and Conquer Approach 時間複雜度 $O(2^n)$ 證明

2. Bottom-up Dynamic Programming Approach

一般人最容易想到的解法，概念是把前兩項相加，達到重複利用的目的，也就是俗稱的Dynamic Programming (以空間換取時間)。

Time Complexity : $O(n)$

class Solution {
public:
    int climbStairs(int n) {
        int first = 1, second = 1;
        for(int i = 0 ; i < n-1 ; i++){
            int temp = first + second;
            first = second;
            second = temp;
        }
        return second;
    }
};

3. Golden Ratio Approach

直接用公式解逼近取得第n項的值。費波那契數列又稱黃金分割數列，因為 1/2 ,2/3 , 3/5 ,5/8 ,8/13 ,13/21 ,21/34 ,...... , 會趨近黃金分割。

$\frac {f_{n+1}}{f_n} \approx a = \frac{1}{2} (1 + \sqrt{5}) = \varphi \approx 1{.}618{...}$

Time Complexity : $O(log n)$，注意這個上界是由 power() recursive multiplication 給出。

class Solution {
public:
    int climbStairs(int n) {
        double estim = 0.4472135955 * pow(1.618033988745, n+1);
        return ( abs(ceil(estim)-estim) < abs(estim-floor(estim)) )? ceil(estim) : floor(estim);
    }
};

References

Computational complexity of Fibonacci Sequence
http://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence

wiki - Fibonacci number
https://en.wikipedia.org/wiki/Fibonacci_number