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:
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
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!
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)
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:
# These are the base cases
# We will store the results to prevent re-computations and do easy lookups
dp = *(n+1)
dp = 1
dp = 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.
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:
first = 0
second = 1
for i in range(2, n + 1):
final = first + second
first = second
second = final
return first + second