斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39
斐波那契数列的公式（和跳台阶的方式不同）
F(0) = 0;F(1) =1;F(n)=F(n-1)+F(n-2);
方法一：使用递归

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

运行效率：
运行时间：1284ms
占用内存：21560k

方法二：循环方式

public class Solution {
    public int Fibonacci(int n) {
        if(n == 0){
            return 0;
        }
        if(n==1)
            return 1;
        int n1 = 0;
        int n2 = 1;
        int total = 0;
        for(int i = 2; i<=n;i++)
        {
            total = n1 + n2;
            n1 = n2;
            n2 = total;
        }
        return total;

    }
}

运行效率：
运行时间：16ms
占用内存：23036k

方法三：

public class Solution {
    public int Fibonacci(int n) {
     int f = 0, g = 1;
        while(n-->0) {
            g += f;
            f = g - f;
        }
        return f;
    }
}

运行效率:
运行时间：19ms
占用内存：22848k