Climbing Stairs

Transitions

Observe that for every stair, you can make two decisions:

  1. Climb one step

  2. Climb two steps

Recurrence tree

Top-down

Top-down can often be implemented by directly modelling the state transitions

def climb_stairs(n):
    memo = {}
    def climb(m):
        if m in memo: return memo[m]
        if m == n: return 1
        if m > n: return 0
        memo[m] = climb(m + 1) + climb(m + 2)
        return memo[m]

The recurrence relation above looks like this:

Bottom-up

Trick: Re-framing the problem A way to convert top-down to bottom-up solutions is to re-frame the problem in a way that only restricts your view of the data to a subset, such as the prefix/suffix/sub-array. Solving this subset gives you the tools to solve larger subsets. A good way to do this is to ask: "Given index i, how do I use the solutions of 0 to i-1 (prefix) or i+1 to n (suffix) solve for index i?"

def climb_stairs(n):
    if n == 1: return 1 # corner case
    stairs = [0] * (n + 1)
    stairs[1] = 1 # reaching stair 1 takes 1 way
    stairs[2] = 2 # reaching stair 2 takes 2 ways
    for i in range(3, n + 1):
        stairs[i] = stairs[i - 1] + stairs[i - 2]
    return stairs[n]

Optimization

From the recurrence relation, we only ever require the previous 2 states, dp(m - 1) and dp(m - 2) to compute dp(m). So, we can store these 2 states as variables instead of using an array.

def climb_stairs(n):
    if n == 1: return 1 # corner case
    s1, s2 = 1, 2 # s1 -> dp(m-2), s2 -> dp(m-1) 
    for i in range(3, n + 1):
        s1, s2 = s2, s1 + s2
    return s2

Keen observers will notice that this is basically the Fibonacci sequence

Last updated