n<=39
思路：递归，然后出(bu)人(chu)意料的超时了，那就直接记录下当之前的每一项，直接递推到第n项。
solution1:
1 class Solution { 2 public: 3 int Fibonacci(int n) { 4 int *p = new int[n+1](); 5 p[0]=0,p[1]=1; 6 for(int i = 2;i<=n;i++) 7 { 8 p[i] = p[i-1]+p[i-2]; 9 } 10 return p[n]; 11 } 12 };
思考：这样需要额外较大的空间复杂度O(n)，其实实际影响当前值的只有两项，因此可以简化空间复杂度。
solution2:
1 class Solution { 2 public: 3 int Fibonacci(int n) { 4 int first = 0,second =1; 5 while(n--) 6 { 7 second = first + second; 8 first = second - first; 9 } 10 return first; 11 } 12 };
思考：额外的空间复杂度O(1)
原文：https://www.cnblogs.com/Swetchine/p/11296987.html