509. Fibonacci Number

Задача

Числа Фибоначчи F(n) образуют последовательность, где каждое число — сумма двух предыдущих, начиная с 0 и 1:

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1

Дано n, верните F(n).

Примеры

Пример 1

Input: n = 2
Output: 1

Пояснение

F(2) = F(1) + F(0) = 1 + 0 = 1.

Пример 2

Input: n = 3
Output: 2

Пояснение

F(3) = F(2) + F(1) = 1 + 1 = 2.

Решение

Решение

// Time Complexity:  O(n)
// Space Complexity: O(n)
var fib = function(n) {
    const memo = [0, 1];
 
    function fibonacci(i) {
        if (memo[i] !== undefined) return memo[i];
        memo[i] = fibonacci(i - 1) + fibonacci(i - 2);
        return memo[i];
    }
 
    return fibonacci(n);
};

Решение 2

function fibonacci(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
 
    let prev = 0; // F(0)
    let curr = 1; // F(1)
 
    for (let i = 2; i <= n; i++) {
        const next = prev + curr;
        prev = curr;
        curr = next;
    }
 
    return curr;
}

Решение 3

function fibonacci(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
 
    let [prev, curr] = [0, 1];
 
    for (let i = 2; i <= n; i++) {
        [prev, curr] = [curr, prev + curr];
    }
 
    return curr;
}