Staircase With K Steps
Medium · rating 1550 · Dynamic Programming
You climb a staircase of n steps, each move covering between 1 and k steps. Read n and k and print the number of distinct ways to reach the top, modulo 1000000007.
Constraints: 1 ≤ n ≤ 105, 1 ≤ k ≤ n
Editorial
Approach
Generalised stair climbing: dp[i] is the number of ways to reach step i, and a move of 1..k means dp[i] = dp[i-1] + … + dp[i-k]. Maintain that sum in a sliding window so each step is O(1).
dp[0] = 1; window = 0
for i in range(1, n+1):
window += dp[i-1]
if i-k-1 >= 0: window -= dp[i-k-1]
dp[i] = window % MODComplexity
Time: O(n). Space: O(n).
Related problems
- Dice Sum Ways — Medium
- House Robber — Hard
- Longest Increasing Subsequence — Hard
- Maximum Product Subarray — Hard
- Subset Sum — Hard
- Unique Grid Paths — Hard