题目描述
楼梯有N阶,上楼可以一步上一阶,也可以一步上二阶。
编一个程序,计算共有多少种不同的走法。
输入输出格式
输入格式:
一个数字,楼梯数。
输出格式:
走的方式几种。
输入输出样例
输入样例#1:
4
输出样例#1:
5
说明
用递归会太慢,需用递推
(60% N<=50 ,100% N<=5000)
也是曾经做过的一道题,单纯复习一下高精斐波那契模板
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define N 5001 using namespace std; },len[N]={}; int read() { ,f=; char ch=getchar(); ; ch=getchar();} +ch-'; ch=getchar();} return x*f; } int fei(int a,int b,int c) { ;i<=max(len[b],len[c]);i++) { f[a][i]+=f[b][i]+f[c][i]; ) { f[a][i+]=f[a][i]/; f[a][i]=f[a][i]%; len[a]=max(len[a],i+); } else len[a]=max(len[a],i); } } int main() { n=read(); f[][]=,f[][]=,len[]=,len[]=; ;i<=n;i++) fei(i,i-,i-); ;i--) printf("%d",f[n][i]); ; }