Climb Stairs

Leetcode link: https://leetcode.com/problems/climbing-stairs/

Question#

There is a staircase with n steps. At each step, we can make a decision to either climb 1 or 2 steps.

Given n steps, find the total number of ways to climb the stairs.

Example:

If n = 0, then there is just one way to climb the stairs. You are already on the top.
If n = 1, then you climb 1 step, so just 1 way.
If n = 2, you can climb 1 step at a time, or 2 steps at once. This gives us 2 ways.
If n = 3, then you can climb 1 step, then 2 steps. 2 steps, then 1 step. Or 1 step all the way. Total = 3 ways.

Implementation#

The key here is to realise that we are making the same duplicate decisions at higher steps. For example, the number of ways to climb when n = 2 steps, is the same as when you are on Step 1 of n = 3.

Visualising this, we realise that f(3) = f(2) + f(1), where f is a function to count the total number of steps. Generalising this, we get f(n) = f(n-1) + f(n-2).

To be efficient, we can store the initial few values and build up our solution from there.

def climbStairs(self, n: int) -> int:
memo = [1,1,2]
if(0 <= n <= 2):
memo[n]
for i in range(3, n + 1):
memo.append(memo[i-1] + memo[i-2])
return memo[n]

To even further optimise the space used, at any point in time, we only need the previous 2 values. We can discard all previous values and just keep track of 2 variables.

By the way, this looks like a solution for fibonacci sequence!