题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
解法1：递归
缺点：需要保存中间重复参数，运算量大
class Solution {
public:
int Fibonacci(int n)
{
if(n<=0)
return 0;
if(n==1)
return 1;
return Fibonacci(n-1) +Fibonacci(n-2);
}
};
不通过：
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为0.00%
缺点是：
需要计算很多的重复参数，例如上面涂颜色部分。
解法2：迭代 （递推）
O(n)的时间复杂度
class Solution {
public:
int Fibonacci(int n)
{
int result[2]={0,1};
int fibNMinusOne=1;
int fibNMinusTwo=0;
int fibN=0;
if(n<2)
{
return result[n];
}
for(unsigned int i=2;i<=n;++i)
{
fibN=fibNMinusOne+fibNMinusTwo;
fibNMinusTwo=fibNMinusOne;//上上次的fibN值
fibNMinusOne=fibN;//上次的fibN值
}
return fibN;
}
};
类似动态规划？：
class Solution {
public:
int Fibonacci(int n)
{
//vector<int> result[n+1];//vector 新建数组出错
int * result=new int[n+1];//新建数组
result[0]= 0;
result[1]= 1;
if(n<2)
{
return result[n];
}
for(unsigned int i=2;i<=n;++i)
{
result[i]=result[i-1]+result[i-2];
}
return result[n];
}
};
解法3： 待完善
O（logn）时间复杂度 涉及矩阵乘法
