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

这简直是太经典的算法题了，我都说倦了。

解法一：简单递归

略

解法二：递归+数组储存递归值

略

解法三：迭代+数组储存 美其名曰 动态规划

略

解法四：两个中间值储存

实际上我们并不需要一整个数组来储存，因为每一次计算我们只需要用到上次和上上次的值。
注意这里 a b 值的更新，并没有用到其他中间变量！

public class Solution {
    public int Fibonacci(int n) {
        if(n<2) return n;
        int a=0, b=1;
        while(n-->1){
            b=b+a;
            a=b-a;
        }
        return b;
    }
}

解法五：斐波那契数列公式法。

直接计算公式即可。
公式和原理见 https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97#2_2
过程略。