斐波那契数列

【题目描述】

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

【代码实现】

传统的递归方式：

这个题可以说是迭代（Iteration） VS 递归（Recursion），

f(n) = f(n-1) + f(n-2)，第一眼看就是递归啊，简直完美的递归环境，这样想着关键代码两三行就搞定了，注意这题的n是从0开始的：

1 class Solution {
2 public:
3     int Fibonacci(int n) {
4        if(n<=1)
5             return n;
6         else
7             return Fibonacci(n-1)+Fibonacci(n-2) ; 
8     }
9 };

然而并没有什么用，测试用例里肯定准备着一个超大的n来让Stack Overflow，为什么会溢出？因为重复计算，而且重复的情况还很严重，举个小点的例子，n=4，看看程序怎么跑的：

Fibonacci(4) = Fibonacci(3) + Fibonacci(2);

= Fibonacci(2) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);

= Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);

动态规划的迭代方式：

 1 class Solution {
 2 public:
 3     int Fibonacci(int n) {       
 4     if(n<=1)
 5     {
 6         returnn;
 7      }
 8     int[] record = newint[n+1];
 9     record[0] = 0;
10     record[1] = 1;
11     for(inti=2;i<=n;i++)
12     {
13        record[i] = record[i-1] + record[i-2];
14     }
15     returnrecord[n];
16     }
17 };

或者：

 1 class Solution {
 2 public:
 3     int Fibonacci(int n) {
 4         int target=0;
 5         if(n<=1)
 6             return n;
 7            int first=0,second=1;
 8         for(int i=2;i<=n;i++)
 9         {
10             target=first+second;
11             first=second;
12             second=target;
13         }
14         return target;
15     }
16 };