题目
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
n<=39
斐波那契数列指的是这样一个数列:
一、递归
一、分析
斐波那契数列的标准公式为:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)
根据公式可以直接写出:
二、代码
public class Solution {
public int Fibonacci(int n) {
if(n<=1){
return n;
}
return Fibonacci(n-1) + Fibonacci(n-2);
}
}
三、 复杂度
时间复杂度:O(2^n)O(2n)
空间复杂度:O(1)O(1)
二、优化递归
递归会重复计算大量相同数据,我们用个数组把结果存起来8!
public class Solution {
public int Fibonacci(int n) {
int ans[] = new int[40];
ans[0] = 0;
ans[1] = 1;
for(int i=2;i<=n;i++){
ans[i] = ans[i-1] + ans[i-2];
}
return ans[n];
}
}
三、动态规划
int a = 0;
int b = 1;
if(n<=1)
{
return b;
}
while(n>0)
{
b+=a;
a=b-a;
n--;
}
return b;