100 #4750. 走楼梯(第15届-202401)

走楼梯(第15届-202401)

Background

走楼梯

题目描述:

一段楼梯共有 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

样例输入:

4 2

样例输出:

5

Limitation

1s, 1024KiB for each test case.