题目描述
见题目
样例
见题目
算法1
(递归写法) $O(n^2)$
这个写法有可能会爆栈,所以我们要注意数据范围
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
long long f(long long n)//不开longlong见祖宗
{
if(n==1) return 1;
else if(n==2) return 1;
else return f(n-1)+f(n-2);
}
int main()
{
long long n;
cin>>n;
cout<<f(n);
return 0;
}
算法2
(递推) $O(n)$
利用a,b,c当成滚动数组计算
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
long long f(long long n)
{
if(n==1) return 1;
else if(n==2) return 1;
else return f(n-1)+f(n-2);
}
int main()
{
long long n,a=1,b=1,c;
cin>>n;
if(n==1)
{
cout<<1;
return 0;
}
else if(n==2)
{
cout<<1;
return 0;
}
for(int i=3;i<=n;++i)
{
c=a+b;
a=b;
b=c;
}
cout<<c;
return 0;
}