LC070 - Climbing Stairs

Problem

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example

Input: n = 2

Output: 2

Explanation: There are two ways to climb to the top.

1. 1 step + 1 step

2. 2 steps

Solution

Naive Recursion

The naive solution is to visit every node and check for both conditions, i.e. 1 and 2 steps using recursion. The problem with this is that it takes $O(2^n)$ time, because there are 2 choices at each node, and there are $n$ nodes. We use $O(n)$ space for the recursive stack, as there are $n$ nodes.

def recurse(n: int) -> int:
	if n < 2:
		return 1
	else:
		return recurse(n-1) + recurse(n-2)
		
def climbStairs(self, n: int) -> int:
	return recurse(n)

Dynamic Programming

Notice that each smaller subtree depends on the larger tree as a whole, compute backwards. Time complexity is $O(n)$ and space complexity is $O(n)$, but can be refined to be $O(1)$ by just using two variables to hold intermediate values instead of an array.

def climbStairs(self, n: int) -> int:
    arr = [0] * (n+1)
    arr[n] = 1
    arr[n-1] = 1
    # Pointer starts from 3rd last element
    ptr = n-2
    while True:
        arr[ptr] = arr[ptr+1] + arr[ptr+2]
        ptr = ptr - 1
        if ptr < 0:
            break
    return arr[0]

Cache — Memoization

Subtrees are repeated, so we can store the results from each subtree so that we don’t have to compute them multiple times. Time complexity using a DP cache is $O(n)$.