题目：斐波那契数列
考点：递归和循环
题目描述：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0），n<=39。
法一：递归法，不过递归比较慢，会超时，所以不考虑
举个小点的例子，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);
+ Fibonacci(1) + Fibonacci(0);
由于我们的代码并没有记录Fibonacci(1)和Fibonacci(0)的结果，对于程序来说它每次递归都是未知的，因此光是n=4时f(1)就重复计算了3次之多。
public class Solution {
public int Fibonacci(int n) {
if(n <= ){
return n;
}else{
return Fibonacci(n-)+Fibonacci(n-);
}
}
}递归法运行时间：1200ms
法二：利用循环
public class Solution {
//求斐波那契数列的前n项和
public int Fibonacci(int n) {
if(n == ){
return ;
}
if(n == || n == ){
return ;
}
int one = ;
int two = ;
int sum = ;
for(int i = ; i < n; i++){
sum = one + two;
one = two;
two = sum;
}
return sum;
}
}循环法运行时间：21ms
法三：动态规划法
public class Solution {
//求斐波那契数列的前n项和
public int Fibonacci(int n) {
//动态规划法
if(n == ) return ;
int one = ;
int two = ;
while(n-- > ){
two = two + one;
one = two - one;
}
return two;
}
}动态规划法运行时间：13ms