斐波那契数列

题目：

写一个函数，输入n，求斐波那契数列的第n项。

思路：

什么是斐波那契数列呢？

斐波纳契数列（Fibonacci Sequence）,又称黄金分割数列.
斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、……
这个数列从第三项开始,每一项都等于前两项之和.

斐波那契数列的表达式如下：

F[n]=F[n-1]+F[n-2] (n>2,F[0]=1,F[1]=1)

解答：

public class Solution {
    public int Fibonacci(int n) {
        if(n==0) return 0;
        if(n==1||n==2) return 1;
        int[] fisequence = new int[n+1];
        fisequence[0]=0;
        fisequence[1]=fisequence[2]=1;
        for(int i=3;i<n+1;i++){
            fisequence[i]=fisequence[i-1]+fisequence[i-2];
        }
        return fisequence[n];
    }
}

如上是最简单的写法，两分钟就出来了，但是这一定不是面试官想看到的。所以我们必须明确题目的考点和最佳实现方法。

优化：

然而，看了大神的写法，发现这道题目就两种思路，没有更多了。

思路一：递归，简洁但是效率不高

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

思路二：循环，O(N）

这种思路和上面我的解法是一样的，但是问题就在于我的解法用到了一个n+1长度的数组来保存了所有的中间结果，但是其实是不需要对中间结果进行保存的，最佳实现可以通过只使用两个变量的空间来实现。即将空间复杂度由O(N）降低为O(1)。

public class Solution {
    public int Fibonacci(int n) {
        if(n==0) return 0;
        if(n==1||n==2) return 1;
        int pre = 1;
        int next =1;
        int result =0;
        for(int i=3;i<n+1;i++){
            result = pre+next;
            pre = next;
            next=result;
        }
        return result;
    }
}