剑指面试题10

题目：现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39

递归很慢

解题思路：避免重复计算，把已经计算过的中间项保存下来。

具体代码：
public class Solution {
public int Fibonacci(int n) {
int f0 = 0;
int f1 = 1;
int f = 0;
if(n == 0){
return 0;
}else if(n == 1){
return 1;
}else{
for(int i = 2;i <=n;i++){
f = f0+f1;
f0 = f1;
f1 = f;
}
return f;
}

}

}