0
已解决
高级天翼
2956 0~~n
经验值：1200 时间限制：1000毫秒
题目描述 Description
现有一个数n，需要从0开始增加，每次可以增加1或2
编一个程序，计算从0增加到n共有多少种不同的方法。
输入描述 Input Description
一个数字n。
输出描述 Output Description
方法数。
样例输入 Sample Input
4
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
用递归会太慢，需用递推
（60% N<=50 ,100% N<=5000)
#include<iostream>
#include<bits/stdc++.h>
#include<cstdio> //头文件
using namespace std;
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
long long a[10002],n;
cin>>n;
a[0]=1;
a[1]=1;
for(int i=2;i<=n;i++){
a[i]=a[i-1]+a[i-2];
}
cout<<a[n];
fclose(stdin);
fclose(stdout);
return 0;
}60分？？？
0
已采纳
中级启示者
要用高精
高加核心
string Plus(string x,string y){ //x+y
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
a[0]=x.length(),b[0]=y.length();
c[0]=max(a[0],b[0]);
for(int i=1;i<=a[0];i++){
a[i]=x[a[0]-i]-'0';
}
for(int i=1;i<=b[0];i++){
b[i]=y[b[0]-i]-'0';
}
int jw=0;
for(int i=1;i<=c[0];i++){
c[i]=a[i]+b[i]+jw;
jw=c[i]/10;
c[i]%=10;
}
if(jw!=0){
c[0]++;
c[c[0]]=jw;
}
string ans="";
for(int i=c[0];i>=1;i--){
ans+=char(c[i]+'0');
}
return ans;
}递推
f[1]="1",f[2]="2";
for(int i=3;i<=n;i++){
f[i]=Plus(f[i-1],f[i-2]);
}f数组要定义成string
0
资深光能
要用高精，n>90就超longlong了
荣光峰在2021-08-14 11:13:19追加了内容
你看这里，围墙重建和他一模一样
荣光峰在2021-08-14 11:15:33追加了内容
区别就是一个是1~n，一个0~n
0
初级天翼
高精度
0
缔造者之神
这道题目和1083差不多，区别在于：
测试点6：
输入1
输出1
1083写出来后，加上特判即可AC。
望采纳！（汪大佬讲得很好）
