斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

n<=39

题解

思路1

递归

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

N一大，栈可能会溢出

思路2

迭代

时间复杂度: O(n)- 空间复杂度: O(N)

public int Fibonacci(int n) {
    if (n == 0)
        return n;

    int[] array = new int[n + 1];
    array[0] = 0;
    array[1] = 1;
    for (int i = 2; i <= n; i++) {
        array[i] = array[i - 1] + array[i - 2];
    }
    return array[n];
}

优化一下，没有必要开一个O(N)的数组

时间复杂度: O(n)- 空间复杂度: O(1)

public int Fibonacci(int n) {
    if (n == 0 || n == 1)
        return n;

    int pre1 = 0;
    int pre2 = 1;
    int res = 0;
    for (int i = 2; i <= n; i++) {
        res = pre1 + pre2;
        pre1 = pre2;
        pre2 = res;
    }
    return res;
}