A46319. 上台阶小瓜想走上一个一共有n级的台阶，由于小瓜的腿长比较特殊，他一次只能向上走1级或者3级或者5级台阶。小瓜想知道他有多少种方法走上这n级台阶，你能帮帮他吗？#输入一行一个整数n（n<=100000），表示一共有n级台阶。#输出一行一个整数，表示小瓜上台阶的方案数对100003取余的结果。#样例输入3样例输出2
填空题
中等
知识点
题目描述
上台阶
小瓜想走上一个一共有n级的台阶，由于小瓜的腿长比较特殊，他一次只能向上走1级或者3级或者5级台阶。小瓜想知道他有多少种方法走上这n级台阶，你能帮帮他吗？#
输入
一行一个整数n（n<=100000），表示一共有n级台阶。#
输出
一行一个整数，表示小瓜上台阶的方案数对100003取余的结果。#
样例输入
3样例输出
2参考答案
#include<iostream>
using namespace std;
long step[1000003] = {0};
int main(){
int N;
cin>>N;
if(N<=0){
return 0;
}
step[0] = 1;
step[1] = 1;
step[2] = 2;
step[3] = 3;
step[4] = 5;
if(N<=5){
cout<<step[N-1]<<endl;
return 0;
}
for(int i=5;i<N;i++){
step[i]= (step[i-1]+step[i-3]+step[i-5])%100003;
}
cout<<step[N-1]<<endl;
}
上一题
下一题