题目说明：

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39

实现如下：

//0 1 1 2 3 5 8 13 21...
//简洁的递归，但是注意消除重复计算项，采用map存储已计算的n的value
class Solution 
{
public:
	map<int, long long> m;
	long long num;
	int Fibonacci(int n) 
	{
		if (n == 0) return 0;
		else if (n == 1) return 1;
		else
		{
			map<int, long long>::iterator it = m.find(n);//查找是否已计算过
			if (m.end() == it)//之前没算过，进行计算，再insert
			{
				num = Fibonacci(n - 1) + Fibonacci(n - 2);
				m.insert(pair<int, long long>(n, num));
				return num;
			}
			else return it->second;//若之前算过，直接get second
		}
	}
};

//O(n)的循环方法，没有什么好解释的...→_→
class Solution 
{
public:
	int Fibonacci(int n) 
	{
		long long res[2] = { 0,1 };
		long long tmp = 0;
		if (n == 0) return 0;
		else if (n == 1) return 1;
		else
		{
			for (int i = 2; i <= n; ++i)
			{
				//空瓶子swap
				tmp = res[0] + res[1];
				res[0] = res[1];
				res[1] = tmp;
			}
			return res[1];
		}
	}
};