P1255 数楼梯
洛谷原题:
题目描述
楼梯有 N 阶,上楼可以一步上一阶,也可以一步上二阶。
编一个程序,计算共有多少种不同的走法。
输入格式
一个数字,楼梯数。
输出格式
输出走的方式总数。
题目分析
可知那层楼的做法就为该值的斐波那契数,但在以普通递归去借时会超出运行时间
如下为一般递归函数
int f(int n) {
if (n == 1 || n == 2)return 1;
else return f(n - 1) + f(n - 2);
}
所以要用高精度数组相加的方法去保存超过long long的值。
#include<bits/stdc++.h>
using namespace std;
int arr[5005][5005],n,len=1;
void f(int n) {
int i;
for (i = 1; i <= len; i++) arr[n][i] = arr[n - 1][i] + arr[n - 2][i];
for (i = 1; i <= len; i++) {
if (arr[n][i] >= 10) {
arr[n][i + 1] += arr[n][i] / 10;
arr[n][i] %= 10;
if (arr[n][len + 1])len++;
}
}
}
int main()
{
int i;
cin >> n;
arr[1][1] = 1;
arr[2][1] = 2;
for (i = 3; i <= n; i++) f(i);
for (i = len; i >= 1; i--)cout << arr[n][i];
return 0;
}