10.1
Idea. Let ways[i] be the number of ways to reach step i.
Recurrence: [math]\displaystyle{ \text{ways}[i]=\sum_{j=1}^{k}\text{ways}[\,i-j\,] }[/math] for i ≥ 1, with the convention ways[0] = 1 and ways[i] = 0 for negative indices.
Iterative DP.
function countWays(n, k):
ways = array of size n+1
ways[0] = 1
for i = 1 .. n:
total = 0
for j = 1 .. k:
if i - j ≥ 0:
total += ways[i-j]
ways[i] = total
return ways[n]
Complexities. Time [math]\displaystyle{ O(nk) }[/math] (two nested loops). Space [math]\displaystyle{ O(n) }[/math]; this can be reduced to [math]O(k)[/math] by keeping only the last
k values in a sliding window.Hence the algorithm counts the exact number of ways to climb [math]n[/math] stairs when up to [math]k[/math] steps can be taken at once, running in [math]O(nk)[/math] time.
Back to
Chapter 10
