Algorithm for Climbing Stairs Problem using Dynamic Programming


In this article, we will cover a famous dynamic programming question, "Climbing Stairs".
This is the first part of the Dynamic Programming Series.(1A) Each category comprises of 4-5 questions.
We will be covering 4 major categories
This is category A: Finding Distinct Ways
Question No 1: Climbing Stairs

What is Climbing Stairs Problem?

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

Climbing Stairs Problem Examples:

Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Intial takes on the question:

  • We need to reach the top of the floor step by step
  • We have to make a choice at every step we take, the choices are: Climb one step or Climb 2 steps
  • We need to tell that in how many ways are there to reach the top.

Now that we have pretty much understood what the question wants we will now understand how to approach it in a step by step manner

Let's try to break the problem down a bit. Just to make things easier to understand and see if we can form some relation!


What if there is are no steps to climb? i.e. if steps = 0, how many ways are there to reach the top? Well obviously zero only!
What if there is only one step to climb i.e. steps = 1, we can take only one step, two steps are not possible, so possible ways = 1.
Now what if we have 2 steps to climb? Following cases are possible:
  • The first way: Take 1 step, now we need to take one more step, how many ways are there for this one step now? Well, 1 only! (We computed it a couple of lines above!)
  • The second way: Take 2 steps, now we need to take 0 more steps, how many ways are there for this 0 step now? Well, we know that too already! Zero!
Recursion Pattern Formed

I guess you must have noticed a pattern by now. For making it sink down inside your brain, I will go through one more example!
Say that we have 4 steps to climb.
Remember at each point we can either take 1 step or take 2 steps, so let's try to understand it now! Let's look at the possibilities:

4--> 1+1+1+1 or 2+1+1 or 1+2+1 or 1+1+2 or 2+2

  • Take 1 step always.
  • Take 2 steps and then take 1 step and 1 more
  • Take 1 step and then take 2 steps and then 1 last!
  • Take 1 step, 1 more step and now 2 steps together!
  • Take 2 steps and again 2 steps to reach quickly!

So this makes a total of 5 distinct ways! But do we really need to calculate this all again and again?
Well this is where Dynamic Programming walks in.
In the example above think of taking 2 steps and then we have 2 more steps to take, we begin to compute ways for them now, but wait before computing it again, we know we have this thing computed already!
This is nothing but the number of distinct ways to climb a staircase with 2 steps! Which is equal to 2. (1+1 or 2+0) Step 1 of dp formulation
Step 2 of dp formulation

So we can safely begin to compute using pre computed results!
  • Stay where ever you are, look one step behind, and look two steps behind, you know you can reach where you are from both these positions!
  • The key intution that we have gained from the examples discussed above are that
  • If we know the number ways to get to the points [n-1] and [n-2] respectively, denoted as n1 and n2
  • Then the total ways to get to the point [n] is n1 + n2.
  • Because from the [n-1] point, we can take one single step to reach [n]. And from the [n-2] point, we could take two steps to get there.
The problem is a classical recursive problem..(FIB)
Where the recursive realtion pans out to be
climbStairs(n) = climbStairs(n-1) + climbStairs(n-2)

Climbing Stairs Problem Python Implementation:

def climbStairs(n): # These are the base cases if n<4: return n # We will store the results to prevent re-computations and do easy lookups dp = [0]*(n+1) dp[1] = 1 dp[2] = 2 # We just need to look 1 step back and two step back for i in range(3,n+1): dp[i] = dp[i-1] + dp[i-2] # returning distinct ways for the given steps. return dp[n]

Notice that we do not actually need to track all the numbers at all times, we just need to know the two guys behind me!

def climbStairs(self, n): if n < 4: return n first = 0 second = 1 for i in range(2, n + 1): final = first + second first = second second = final return first + second
        


Comments



Contact Us
Need any Technical Help Online
Message Us
Search

Play 2048 Game Online


Search Tags

    Climbing Stairs Dynamic Programming Problem simple explanation

    Climbing Stairs Problem Example using Python