题目：斐波那契数列
题目描述：
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39
题目思考：
首先，我们需要知道的是斐波那契数列是什么？
image.png
既然我们知道了什么事斐波那契数列，那我们最先想到的方法就是通过数列的通项公式，通过递归的方式来计算n的对应值F(n).
题目思路一：
最简单最之际的方法，也是我们最先想到的，但是却是最不推荐的，通过递归的方式，这种方式占用时间和内存都不是最优的。
class Solution {
public:
int Fibonacci(int n) {
if(n <= 0) return 0;
if(n == 1|| n == 2) return 1;
return Fibonacci(n-1) + Fibonacci(n-2);
}
};
题目思路二：
题目思考中的方式，通过中间变量的，迭代循环，不断叠加，最终计算出数据结果。
class Solution {
public:
int Fibonacci(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
int temp1 = 0,temp2 = 1;
int result = 0;
for(int i = 2; i<= n; i++){
result = temp1 + temp2;
temp1 = temp2;
temp2 = result;
}
return result;
}
};
题目思路三：
在网上看的，动态规划的方式，我自习看了一下，其实和递归循环的方式有些类似，唯一的差别就是将中间存贮结果的变量省略，通过两个数据加减实现最终的这个算法。
方式一：
class Solution {
public:
int Fibonacci(int n) {
int f = 0, g = 1;
while(n--){
g = g + f;
f = g - f;
}
return f;
}
};
方式二：
class Solution {
public:
int Fibonacci(int n) {
if(n <= 0) return 0;
int f = 0, g = 1;
while(n-- > 1){
g = g + f;
f = g - f;
}
return g;
}
};
两种方式的差别在于返回的是g还是f：
第一种代码其实多循环了一次，最终的结果是n的下一阶，所以我们没有输出g，而是输出f。
第二种代码就是正合适的循环次数，最终结果就是n，所以我们就输出g，而不是输出f。
