动态规划解决斐波那契数列问题

显然使用的递归方法解决斐波那契数列问题，效率并不高，运用递归方法时间复杂度和空间复杂度是很大的。

接下来我会把我学习到的一种效率较高并且其空间复杂度较小的方法介绍一波：

动态规划：由底向顶逐步迭代求得斐波那契数列的第n项

传统的解决方法是运用公式：F（n-1）+ F（n+1）；而这种方法是运用g，f 两个变量分别的的迭代变换，即：

g = g + f ;
f = g - f ;
例：g = 1； f = 0；
1.
g = 1 + 0 = 1；
f = 1 - 0 = 1；
2.
g = 1 + 1 = 2；
f = 2 - 1 = 1；
3.
g = 2 + 1 = 3；
f = 3 - 1 = 2；
依次迭代计算，最后的g就是我们所要求的斐波那契数列第n项

#include<stdio.h>
void Fibonacci(int n){
 int i;
 int g = 1;
 int f = 0;
 for(i = 0;i < (n - 1);i++){
  g = g + f;
  f = g - f;
 }
 printf("斐波那契第%d项是：%d",n,g);
}
int main(){
   Fibonacci(7);
} 

这种方法的时间复杂度T（n）= O（n），并且空间复杂度也缩小为O（1）（只有常数项相加）

接下来我还会把我所学写成博客分享给大家，希望我们共同学习