• Starting from 0, we can either climb one or two stairs.
• If we climbed one, then we are on stair (1). If we climbed 2, then we are on stair (2).
• Repeat the process from each one of those stairs
• Every time you reach stair (n) increase a counter.

Schematically this process looks like the following (Assume n = 3):

Top-down approach

Recursively, in this top down approach:

• The base case is when we reach \(n\), in which case we return 1, or exceed \(n\), in which case we return 0 (see above tree).
• The recursive relationship is that at each step \(k\) we sum the results of the subproblems \(k+1\) and \(k+2\).

def climb_stairs(n: int) -> int:
    def helper(k):
        if k == n:
            return 1
        if k > n:
            return 0
        return helper(k + 1) + helper(k + 2)

    return helper(0)

We can run the first example as follows:

climb_stairs(3)

## 3

Of course, we can think of this problem in a bottom-up fashion as well. To reach stair n, we can either climb one stair from stair n-1, or two stairs from stair n-2 (this is the recursive relationship)

• Repeat until n = 1 or n=2 (these are the base cases:

• If n = 1, we can only get there by climbing one stair from the beginning. Hence return 1.

• If n = 2, we can get there either by climbing 1 stair from stair 1, and by climbing 2 stairs from the beginning. Hence return 2.

The Python bottom-up solution is as follows:

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    return (climb_stairs(n - 1)) + (climb_stairs(n - 2))

Now in the Figure above, you can notice that we are actually computing how many times we can reach the number “3” from node “2” twice (purple boxes). If the N was larger than 3, we would be performing repeated computations in an exponential fashion. Why waste this extra computation?

What if we store the solution for each node we solve in a hashmap and not call the recursive function again? For instance, we can re-write the previous solution as follows:

mem = {} 
def climb_stairs(n: int) -> int:
    if n <= 2: return n
    if n in mem: return mem[n]
    mem[n] = (climb_stairs(n-1))+ (climb_stairs(n-2))
    return mem[n]

The time complexity of this solution is \(O(2^N)\) without memoization. With memoization is \(O(N)\), as we only do \(N\) recursive calls.