The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

    F(0) = 0, F(1) = 1
    F(n) = F(n - 1) + F(n - 2), for n > 1.
    

    Given n, calculate F(n).

    運用費波那契數來表示 F(n),使每個數為前兩個數的合,從 0 和 1 開始:
    
    F(0) = 0, F(1) = 1
    F(n) = F(n - 1) + F(n - 2), for n > 1.
    
    給予 n 來計算 F(n) 的結果。
    

    Example 1:

    Input: n = 2
    Output: 1
    Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
    

    Example 2:

    Input: n = 3
    Output: 2
    Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
    

    Example 3:

    Input: n = 4
    Output: 3
    Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
    

    Solution:
    1. 判斷 f(0) = 0 為 0, f(1) = 1 為 1。
    2. 每一輪的 f(n) 套入 fib function 拆分為 f(1) 與 f(0) 的組合後進行加總。

    Code.1:

    var fib = function(n) {
        if (n <= 0) {
            return 0
        }  else if (n === 1) {
            return 1
        }  else {
            return fib(n - 1) + fib(n - 2)
        }
    }
    

    FlowChart:
    Example 1

    Input: n = 2
    
    fib(2 - 1) = fib(1) = 1
    fib(2 - 2) = fib(0) = 0
    return fib(1) + fib(0) = 1
    

    Example 2

    Input: n = 3
    
    fib(3 - 1) = fib(2) => fib(2 - 1) = fib(1) = 1
    fib(3 - 2) = fib(1) = 1
    return fib(2) + fib(1) = 1 + 1 = 2
    

    Example 3

    Input: n = 4
    
    fib(4 - 1) = fib(3) => fib(2) + fib(1) => (fib(1) + fib(0)) + fib(1) => 1 + 1 = 2
    fib(4 - 2) = fib(2) => fib(1) + fib(0) = 1
    return fib(3) + fib(2) => 2 + 1 = 3
    

    Code.2: dp

    var fib = function(n) {
        let dp = [0, 1];
    
        for (let i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    };