剑指Offer练习题2：斐波那契数列

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

//解法一：常规解法
//时间复杂度：O(2^n)
//空间复杂度：O(1)
public class Solution {
//fib(n) = fib(n-1) + fib(n-2) n>=3;		
    public int Fibonacci(int n) {
		if(n==0 || n==1)
			return n;//第0项和第1项
		return Fibonacci(n-1) + Fibonacci(n-2);//用递归求
    }
}

//解法二：优化存储
//时间复杂度：O(n)
//空间复杂度：O(1)
public class Solution {
//fib(n) = fib(n-1) + fib(n-2) n>=3;
    public int Fibonacci(int n) {
		if(n==0 || n==1)
			return n;//第0项和第1项
		int sum=1;
		int before = 0;//相当于用了两个指针指向一个数组，sum指向后一个数，before指向前一个数
		for(int i=2; i<=n; i++){//从数组下标为2开始往后推，加出要找的数
			sum = sum + before;
			before = sum - before;
		}
		return sum;
    }
}

解法二图解：