题解 | #JZ7-斐波那契数列#

一、递归实现
时间复杂度：O(2^n)
空间复杂度：O(1)

    public int Fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }

二、动态规划
时间复杂度：O(n)
空间复杂度：O(1)

    public int Fibonacci(int n) {
        int first, second = 0, sum = 1;
        for (int i = 1; i <= n; i++) {
            first = second;
            second = sum;
            sum = first + second;
        }
        return second;
    }