Fibonacci

题目链接：Fibonacci

In mathematics, the Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

f(n) = f(n-1) + f(n-2)
f(1) = 0, f(2) = 1

Recursion Solution:

public int fibonacci(int n) {
    if (n == 1) {
        return 0;
    }
    
    if (n == 2) {
        return 1;
    }
    
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Runtime: exponential, 2^n.
Space: O(n), stack layers

Recursion with memory

passed with 1620 ms

public int fibonacci(int n) {
    if (n == 1) {
        return 0;
    }
    
    if (n == 2) {
        return 1;
    }
    
    int[] mem = new int[n];
    Arrays.fill(mem, -1);
    mem[0] = 0;
    mem[1] = 1;
    
    return fibonacciHelper(n, mem);
}

private int fibonacciHelper(int n, int[] mem) {
    if (mem[n - 1] >= 0) {
        return mem[n - 1];
    }
    
    int res = fibonacciHelper(n - 1, mem) + fibonacciHelper(n - 2, mem);
    mem[n - 1] = res;
    
    return res;
}

Runtime: O(n)
Space: O(n)

DP solution

passed with 1563 ms

public int fibonacci(int n) {
    int first = 0;
    int second = 1;
    if (n == 1) {
        return first;
    }
    if (n == 2) {
        return second;
    }
    int res = 0;
    for (int i = 3; i <= n; i++) {
        res = first + second;
        first = second;
        second = res;
    }
    
    return res;
}

Runtime: O(n)
Space: O(1)