## 費波那契數列解法總整理

### 一、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, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 (0不是第一項，而是第零項。)

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

#### 1. Top-down Divide and Conquer Approach

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

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

$\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