The Blind 75 Leetcode Series: Climbing Stairs

Today, we will be working on 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?

We are only given one int, n, so the specifications would be around this number.

  1. What range of numbers are we going to see?
  2. Are we only expecting integers? What happens when non-integers show up?
  3. what happens to negative numbers?

If the interviewer tells us that the range goes from 0 to some finite large number, and we are only expecting positive integers, then we have

You are climbing a staircase. It takes n steps to reach the top where n is a positive integer ranging from 0 to a finite number.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Let’s get started.

In order to get to n steps, we want to first know how many unique ways to get to n-1, to know about n-1, we want to know how many unique ways to get to n-2. We eventually reach the point where we want to figure out how many unique ways to get to 1 step, even 0 step.

From there, we can build it up and get to n again. We are facing a dynamic programming type of problem.

We start with 1 step. We know there is only 1 unique way to get to 1 step: by climbing only 1 step. For 2 steps, we now have 2 ways: by climbing 1 step twice, or by climbing 2 steps in a single run.

For 3 steps, we can build from 1 step which takes another 2 steps, or build from 2 steps which takes another 1 step. The total unique ways to get to 3 steps is sum(unique ways to get to 1 step, unique ways to get to 2 steps) = 1 + 2 = 3 ways.

Similarly for 4 steps, we take 1 step from 3 or take 2 steps from 2, so the total unique ways = sum (unique for 3, unique for 2) = 3 + 2 = 5.

This then becomes a Fibonacci sequence, where the next number is the sum of previous 2: [1, 1, 2, 3, 5, 8……].

Okay, so we just want to build this up. We form a list with length of n, where n is the steps we need to climb to. Then we start filling the number up.

The first element, 1, is the number of unique ways to get to 0 step. The second element, also a 1, is the number of unique ways yo get to 1 step. You know the drill for the rest.

To put it in code, it looks like:

def climbStairs(n):
if n <= 2:
return n
steps = [0] * (n + 1) # to include 0 step
steps[0], steps[1] = 1, 1 # to get to 0 step and 1 step
for i in range(2, n+1):
steps[i] = steps[i-1] + steps[i-2]
return steps[-1] # last element is the n-th step

What’s the time complexity we are looking at? We go through the list once, so it’s O(n).

We don’t really have a faster way to solve this problem, but we sure can deal with it in a recursive way.

Again, a recursive function requires a base condition and a way to breakdown or build up to the answer.

For our problem, we know the base condition is when n = 1 or n =0, where we just return 1. From there, we sum up the previous 2 answers.

# base condition:
if n <= 1:
return 1
# breakdown
else:
return steps[n-2] + steps[n-1]

To put everything in code:

def recursive(n):
if n <= 1:
return 1
else:
return recursive(n-1) + recursive(n-2)
def climbStairs(n):
return self.recursive(n)

What’s the time complexity this time? For each recursion, we need to calculate 2 more recursions. So we are looking at O(n²) total time complexity. This is definitely not a better answer in terms of performance.

There IS a way to make it perform better by introducing a tracker, much like how we track the steps in the dynamic programming approach, but honestly, the first approach is simple enough. I’d recommend looking it up if you’d like to know more in the discussion section. Look for any memoization in the topic.

That’s it! Another problem down.

Buy my a coffee: https://www.buymeacoffee.com/jonathanckz

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store