首页 > 代码库 > 洛谷——P1255 数楼梯
洛谷——P1255 数楼梯
题目描述
楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
输入输出格式
输入格式：
一个数字，楼梯数。
输出格式：
走的方式几种。
输入输出样例
输入样例#1：
4
输出样例#1：
5
说明
用递归会太慢，需用递推
（60% N<=50 ,100% N<=5000)
也是曾经做过的一道题，单纯复习一下高精斐波那契模板
#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#define N 5001using namespace std;int n,f[N][N]={0},len[N]={0};int read(){ int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f;}int fei(int a,int b,int c){ for(int i=1;i<=max(len[b],len[c]);i++) { f[a][i]+=f[b][i]+f[c][i]; if(f[a][i]>9) { f[a][i+1]=f[a][i]/10; f[a][i]=f[a][i]%10; len[a]=max(len[a],i+1); } else len[a]=max(len[a],i); }}int main(){ n=read(); f[1][1]=1,f[2][1]=2,len[0]=1,len[1]=1; for(int i=3;i<=n;i++) fei(i,i-1,i-2); for(int i=len[n];i>=1;i--) printf("%d",f[n][i]); return 0;}
洛谷——P1255 数楼梯
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。