Given n stairs and an integer k, return the number of ways to reach the top if each move can climb between 1 and k steps. Pattern focus: Linear Recurrence DP. The answer at each position is the sum of the previous k states.
n = number of stairs, k = maximum step size
number of distinct ways to reach the top
Example 1:
Input:
n = 4 k = 2
Output:
5
Explanation:
This matches the classic 1-or-2 step staircase count.
Example 2:
Input:
n = 4 k = 3
Output:
7
Explanation:
Allowing a 3-step jump increases the count.