public int fibonacci(int n) {
if (n==1||n==0){
return n;
}else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
时间复杂度:o(2n) 空间复杂度:o(1)
public int Fibonacci(int n) {
int [] nums=new int[40];
nums[0]=0;
nums[1]=1;
for (int i = 2; i <= n; i++) {
nums[i]=nums[i-1]+nums[i-2];
}
return nums[n];
}
时间复杂度:o(n) 空间复杂度:o(n)
分析 其实我们可以发现每次就用到了最近的两个数,所以我们可以只存储最近的两个数
sum 存储第 n 项的值 one 存储第 n-1 项的值 two 存储第 n-2 项的值
public class Solution {
public int Fibonacci(int n) {
if(n == 0){
return 0;
}else if(n == 1){
return 1;
}
int sum = 0;
int two = 0;
int one = 1;
for(int i=2;i<=n;i++){
sum = two + one;
two = one;
one = sum;
}
return sum;
}
}
时间复杂度:o(n) 空间复杂度:o(1)
sum 只在每次计算第 n 项的时候用一下,其实sum,tow,one本身就有一个算数和的运算关系,所以其实还可以利用 sum 存储第 n-1 项,例如当计算完 f(5) 时 sum 存储的是 f(5) 的值,当需要计算 f(6) 时,f(6) = f(5) + f(4),sum 存储的 f(5),f(4) 存储在 one 中,由 f(5)-f(3) 得到
public int Fibonacci(int n) {
if(n == 0){
return 0;
}else if(n == 1){
return 1;
}
//用于存放n-1时候的值
int sum=1;
int one=0;
for (int i = 2; i <= n; i++) {
sum=sum+one;
one=sum-one;
}
return sum;
}