P1255 数楼梯
题目描述
楼梯有 N 阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
对于60% 的数据，N≤50；
对于100% 的数据，1≤N≤5000。
思路：每次有2种方法上楼梯，要么上一阶，要么上二阶。
第一种：得50分的做法是可以用递归来解：
点击查看代码
int dfs(int n)
{
if (n == 1) return 1;
else if (n == 2) return 2;
else dfs(n - 1) + dfs(n - 2);
}
数据小的时候用递归才可以AC
第二种：得60分做法是使用斐波拉契数列
点击查看代码
void solve()
{
long long fn[5005];
long long n;
cin >> n;
memset(fn, 0, sizeof(fn));
fn[1] = 1;
fn[2] = 2;
for (long long i = 3; i <= n; i++) {
fn[i] = fn[i - 1] + fn[i - 2];
}
cout << fn[n];
}
点击查看代码
int main()
{
cin >> n;
int t = 1;
int a[10000],b[10000],c[10000];
a[1] = 1;
b[1] = 2;
if(n==1) cout<< 1;
else if(n==2) cout << 2;
else {
for(int i = 3; i <= n; i ++){
for(int i = 1; i <= t; i ++) c[i] = a[i] + b[i];
for(int i = 1; i <= t; i ++) c[i+1] += c[i] /10,c[i] %= 10;
if(c[t+1] != 0) t ++;
swap(a,b);
swap(b,c);
memset(c,0,sizeof(c));
}
for(int i = t; i >= 1; i--) cout << b[i];
}
cout << endl;
return 0;
}