题目说明：
大家都知道斐波那契数列，现在要求输入一个整数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]; } } };