Climbing Stairs

Transitions

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

  1. Climb one step

  2. Climb two steps

Recurrence tree

We don't count leaves that end with values where v > n. We can also memoize the results of sub-trees such as 2, reducing the computation of the right sub-tree to a O(1)O(1) lookup.

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:

dp(m)={1,m==n0,m>ndp(m+1)+dp(m+2)dp(m) = \begin{cases} 1, m == n\\ 0, m > n \\ dp(m + 1) + dp(m + 2) \end{cases}

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?"

By re-framing the problem, we will notice that if we are index mm and we have computed the optimal solution for 0..māˆ’10..m-1 (prefix), then we can obtain the optimal solution for mm using the following recurrence:

dp(m)={1,m=12,m=2dp(māˆ’1)+dp(māˆ’2)dp(m) = \begin{cases} 1, m = 1\\ 2, m = 2\\ dp(m-1) + dp(m - 2) \end{cases}

Trick: Interpreting recurrence relations Define what dp(i)dp(i) means and read the recurrence in terms of that definition. For instance, the above can be interpreted as: dp(m)dp(m) is the number of ways to reach step mm If m=1m = 1, then it means we can only take 1 step to reach it (i.e. 1 way) If m=2m = 2, then we can either take 2x1 step or 1x2 steps to reach it (i.e. 2 ways) Otherwise, the number of ways to reach step mm is by stepping once from māˆ’1m-1 or stepping twice from māˆ’2m-2

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.

Optimization: nn-state caching If your recurrence relies on a finite number of nn states only, we can use nn variables to represent these states, removing the need for 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