斐波那契数列
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
n<=39
第一种
最容易想到的方式:
使用递归的方式,自底向上
public class Solution {
public int Fibonacci(int n) {
if(n == 0){
return 0;
}
if(n==1){
return 1;
}
return Fibonacci(n-1)+Fibonacci(n-2);
}
}
优化思路:
一:使用数组存储
优化,我们使用数组来存,但是效果不明显
public class Solution {
int[] arr = new int[40];
public int Fibonacci(int n) {
if(n == 0){
return 0;
}
if(n==1){
return 1;
}
arr[n] = Fibonacci(n-1)+Fibonacci(n-2);
return arr[n];
}
}
优化思路二:
非递归,使用循环方式,每次存储n-1以及n-的值,值存储需要用到的值,那么就可以进行计算
考虑到每一次只存储n-1以及 n-2个数,所以可以只存储前一次计算的前两个值
public class Solution {
public int Fibonacci(int n) {
if(n == 0){
return 0;
}
if(n==1){
return 1;
}
int a=0,b=1,c=0;
//a 代表n-2的值,b 代表n-1的值
for(int i = 2 ; i<=n ;i++){
c = a+b;
a = b;
b = c;
}
return c;
}
}
网友评论