题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
费波那契数列（意大利语：Successione di Fibonacci），又译费波拿契数、斐波那契数列、斐波那契数列、黄金分割数列。
在数学上，费波那契数列是以递归的方法来定义：
F0 = 0 (n=0)
F1 = 1 (n=1)
Fn = F[n-1]+ Fn-2
解决思路
1）递归，按照定义直接写
简单，开销大，时间比较长
public class Solution {
public int Fibonacci(int n) {
if(n == 0){ //递归终止条件
return 0;
}else if(n == 1 ||n==2){
return 1; // 给出递归终止的处理办法
}
// 相同重复逻辑，分解问题的规模，自己调用自己
return Fibonacci(n-2)+Fibonacci(n-1);
}
}
2）用循环，不用递归，最佳解
public class Solution {
public int Fibonacci(int n) {
int a = 1,b = 1,c = 0;
if(n < 0){
return 0;
}else if( n == 1||n == 2 ){
return 1;
}else{
for (int i = 3; i <= n;i++){
c = a+b;
b = a;
a = c;
}
return c;
}
}
}
题外话：算法我个人的理解，是一种思想，也是一种规律，分析出了规律，虽然我也是站在巨人的肩膀上。
