[toc]
题目描述
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第1项是1)。
n<=39
思路以及解答
斐波那契数列大家都知道:
直接暴力
思路很直接,利用函数进行递归即可。
public class Solution {
public int Fibonacci(int n) {
if(n==0){
return 0;
}else if(n==1){
return 1;
}else{
return Fibonacci(n-1)+Fibonacci(n-2);
}
}
}
重复利用结果
直接递归会造成很多重复的计算,要是我们把计算结果先存起来,使用的时候再调用,那就可以优化。
public class Solution {
public int Fibonacci(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
int[] nums = new int[n + 1];
nums[0] = 0;
nums[1] = 1;
for (int i = 2; i <= n; i++) {
nums[i] = nums[i - 1] + nums[i - 2];
}
return nums[n];
}
}