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!