70. Climbing Stairs

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?

Constraints:

• 1 <= n <= 45

Notice that the problem possesses the optimal substructure property. Let $OPT(n)$ be the number of distinct ways to climb to the $n$th step.

• For $n = 1$, there is only 1 way: we take a single step.
• For $n = 2$, there are 2 ways: we either take 2 steps at once, or we take 2 single steps.
• We have $OPT(n-1)$ ways to climb to the $n-1$th step, and for each way, we take one further step to climb $n$ steps in total.
• We have $OPT(n - 2)$ ways to climb to the $n - 2$th step, and for each way, we take 2 steps to climb $n$ steps in total.

Thus, we have $OPT(n) = OPT(n - 1) + OPT(n - 2)$. Our base cases occurs when $n = 1$ or $n = 2$, so the full Bellman Equation is

Bottom-up

We first store all the solutions in a hash table, so they can be accessed in constant time. Then we work our way up from $n = 1$ until we reach the desired step number, following the Bellman Equation:

def climbStairs(n: int) -> int:
	solution = {}
	
	for step in range(1, n + 1):
		if step == 1 or step == 2:
			solution[step] = step
		else:
			solution[step] = solution[step - 1] + solution[step - 2]
	
	return solution[n]

Time Complexity

This is a non-recursive bottom-up approach, so we calculate the time complexity of the for loop. Each iteration takes constant time (if statement and assignments with constant lookup time of the hash table), and there are $n$ iterations. Thus, the total complexity is in $\mathcal{O}(n)$.

Space Complexity

We store the number of distinct ways to reach each step below $n$, which is constant. Since there are $n - 1$ elements we must store, the total space complexity is $\mathcal{O}(n)$.

An Optimisation

Notice that each call only uses the previous 2 ways—and we only care about the very last step! Thus, there is no need to store the distinct ways for every step, and we can store only the previous 2 steps.

def climbStairs(n: int) -> int:
	if n < 3: return n
	
	minus1, ways = 1, 2
	for step in range(3, n + 1):
		minus1, ways = ways, ways + minus1
	
	return ways

We now have the same time complexity of $\mathcal{O}(n)$ but a space complexity in $\mathcal{O}(1)$!