December 27, 2021

509. Fibonacci Number

Solution1: Recursion

Time = 1 + 2 + 4 + 8 + … + 2(n-1) = P(2^n)
Analysis：画 Recursion Tree: 分析每层有多少 node？

Space = O(n)
Analysis：call stack 多少层？(level of recursion tree)

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

Solution2: Recursion (with memorization)

Time = O(n), Space=O(n).

class Solution {
    public int fib(int n) {
        int[] memo = new int[n + 1]; // note: init an n+1 array.
        return fib(n, memo);
    }
    
    private int fib(int n, int[] memo) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else if (memo[n] > 0) {
            return memo[n];
        } else {
            memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
            return memo[n];
        }
    }
}

Solution3: DP solution with O(n) space

Time = O(n), Space=O(n).

class Solution {
    public int fib(int n) {
        if (n <= 0) {
            return 0;
        }
        int[] array = new int[n + 1]; // note: init an n+1 array.
        array[0] = 0;
        array[1] = 1;
        for (int i = 2; i <= n; i++) {
            array[i] = array[i - 2] + array[i - 1];
        }
        return array[n];
    }
}

Solution4: DP solution with O(1) space

Time = O(n), Space=O(1).

class Solution {
    public int fib(int n) {
        int a = 0; 
        int b = 1;
        if (n <= 0) {
            return 0;
        }
        for (int i = 1; i < n; i++) {
            int tmp = a + b;
            a = b;
            b = tmp;
        }
        return b;
    }
}