当前位置:首页 > 递推 > 正文
洛谷P1192台阶问题
2570+

题目大意:有N级的台阶,你一开始在底部,每次可以向上迈最多K级台阶(最少1级),问到达第N级台阶有多少种不同方式。

输入输出格式

输入格式:

输入文件的仅包含两个正整数N,K。

输出格式:

输入文件stair.out仅包括1个正整数,为不同方式数,由于答案可能很大,你需要输出mod 100003后的结果。

输入输出样例

输入样例#1:

5 2

输出样例#1:

8

说明

对于20%的数据,有N ≤ 10, K ≤ 3;

对于40%的数据,有N ≤ 1000;

对于100%的数据,有N ≤ 100000,K ≤ 100。

解题思路

爬楼梯的升级版,当前阶方案数可以由前面k阶的方案数累加得来。

a[i] = a[i-k] + a[i-k+1] + … + a[i-1]

下标小于0,这是现实中不可能的,故方案数是0;下标为0,即还没开始走,方案数是1;下面为整数,方案数记录在a[i]中。

程序实现

About

坚决不Copy代码!

本文标签:,

洛谷P1192台阶问题:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!