A33641. 走楼梯
填空题
困难
知识点
题目描述
走楼梯
题目描述
一段楼梯共有n 阶，小明每次最少走1 阶，最多走k 阶，请问小明共有多少种不同的走法可以走完这n 阶楼梯。
例如：n = 4，k = 2；楼梯共有4 阶，小明每次最多走2 阶；
有如下走法：
第一种：第一次走1 阶，第二次走1 阶，第三次走1 阶，第四次走1 阶；
第二种：第一次走1 阶，第二次走1 阶，第三次走2 阶；
第三种：第一次走1 阶，第二次走2 阶，第三次走1 阶；
第四种：第一次走2 阶，第二次走1 阶，第三次走1 阶；
第五种：第一次走2 阶，第二次走2 阶。
所以小明共有5 种不同的走法可以走完4 阶楼梯。
输入描述
一行输入两个整数n（1≤n≤5000）和k（1≤k≤10），分别表示这段楼梯的阶数及每
次最多可以走的楼梯阶数，整数之间以一个空格隔开
输出描述
输出一个整数，表示小明走完 n 阶楼梯共有多少种不同的走法
样例输入：
4 2
样例输出
5
参考答案
#include <bits/stdc++.h>
using namespace std;
int a[5005];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1,t=0;i<=k;i++){//初始化前k阶
a[i]=1+t; t+=a[i];
}
for(int i=k+1;i<=n;i++){//代入公式递推
a[i]=0;
for(int j=1;j<=k;j++){
a[i]+=a[i-j];
}
}
cout<<a[n];
return 0;
}
上一题
下一题