LeetCode Js-509. Fibonacci Number

    AllenLi
    LeetCode Js-Optimization

    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];
};

    Related Posts