[Leetcode] Fibonacci Number

509. Fibonacci Number

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 0and 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).

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.

Constraints:

0 <= n <= 30

How to approach?

Recursion

function fib(n: number): number {
    if (n === 0) return 0;
    if (n === 1) return 1;

    return fib(n - 1) + fib(n - 2)
};

1. set base case for 2 elements
2. return the sum of the recursion result.

summary

use 2^n time complexity.

Bottom-Up Approach using Tabulation

function fib(n: number): number {
    if (n === 0) return 0;
    if (n === 1) return 1;

    let map = new Map()
    map.set(0, 0)
    map.set(1, 1)
    for (let i = 2; i <= n; i++) {
        map.set(i, map.get(i - 1) + map.get(i - 2))
    }
    return map.get(n)
};

1. return early when n is less than 1.
2. create map to set index and value.
3. for loop will start from 2, and iterate including n.
4. set the key as index and value as the sum of previous value and i-2 value.
5. lastly return the value of key n.

summary

use the base cases, and map structure to save the key value.

Top-Down Approach using Memoization

function fib(n: number): number {
    const memo: number[] = new Array(n + 1).fill(undefined);
    return fibHelper(n, memo);
}

function fibHelper(n: number, memo: number[]): number {
    if (n === 0) return 0;
    if (n === 1) return 1;

    if (memo[n] !== undefined) {
        return memo[n];
    }

    memo[n] = fibHelper(n - 1, memo) + fibHelper(n - 2, memo);
    return memo[n];
}

1. create helper function to take n and memo array.
2. when n is less than 1, then return the n.
3. when memo's nth element is not undefined then return the element directly.
4. set memo nth element as caculated result, it happened recursively by adding n-1 th element result and n-2 th element result.
5. lastly return the memo's nth element.
6. in the original function, create the memo array which length is n+1 and fill it with undefined.
7. return the result of helper function which sum up all the results.

summary

use the array to save the recursive calculation result to use it later. and return the last element in the array.

Iterative Bottom-Up Approach

function fib(N: number): number {
    if (N <= 1) {
        return N;
    }

    let current = 0;
    let prev1 = 1;
    let prev2 = 0;

    for (let i = 2; i <= N; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return current;
}

1. when N is less than 1 then return the N.
2. Set current and prev1,prev2 for initialization.
3. in for loop, starting with 2, current will be prev1 + prev2, and set the pre2 as prev1, prev1 as current.
4. lastly return the current.

summary

this is using the 2 previous values to calculate current value. in this case, we don't need to save in array or map but using two variables for calculation. it benefits space complexity.