[Solution]Problem 56:Climbing Stairs[Amazon]

Dynamic Programming, Logic, Recursion, Math

Sep 16, 2022

To learn more about the newsletter, check our detailed About Page + FAQs

To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.

Recommend this publication to Substack over here

I know you’ve been hungry for this solution.

I can hear your stomach grumbling from over here.

It’s time to eat.

This problem can be found as problem 70. Climbing Stairs on Leetcode.

Problem

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?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 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

Constraints:

1 <= n <= 45

You can test your solution here

I have some really interesting information for you at the end. Use that to show off in your interviews and get those bonus points.

Step 1: Looking for patterns

There are a few things about this question-

It’s simple to understand.
We can break this problem into different sub-parts. When climbing stairs, the act of climbing each individual stair is identical, whether you’re on steps 1,5, or 10. Assuming of course there are more steps left to climb at each of these points.

This points to a recursive sub-structure. We don’t know what the exact recurrence relations are at this point. We will figure them out. How do we do this?

When starting off with a question like this, I like to start playing with small test cases to see if I can spot a pattern. This is a technique that you will see me use often in this newsletter, especially with questions that involve math/recursion. To get better with this for recursion specifically, check out my post on Mathematical Induction and Recursion.

Technology Made Simple

Recursion- A mathematical perspective [Math Monday]

Hello hello reader, Hope your week is off to a groovy start. To make it even better, we will be covering the theory behind recursion. I know Recursion is something that scares a lot of you, so we will cover it. It can be a very comprehensive topic, so we will split it up into multiple posts. This post will help you understand the Math behind recursion. W…

3 years ago · 2 likes · Devansh

So let’s do that.

Step 2: Testing a few Sample inputs

So what does our expected output look like?

The next smallest input is 4. With n=4, we end up with a result of 5. With n=5, we will end up with 8. You can verify these for yourself if you’d like. The numbers are starting to get too big for me, so this is where I would stop and take a step back.

Okay, so where to go from here? Let’s go back to analyzing the structure of this problem.

Let’s say we’re at step n. To get here, there are only two possible steps we could have taken- (n-1) and (n-2). Regardless of how we got to these, we can only use one of these to get to n directly.

This is true for every n that is not 1 or 2 (since both of these would lead to n-1==0 and n-2==0 respectively). So these 2 become our base cases. Neat. That’s a huge step in finding our recurrence relation. Now for the main relation.

Step 3: Finding a Recurrence Relation

We already know that we can only get to step n from either step n-1 or n-2. What else can we figure out?

Let’s say that we were going through n-1. We know that no matter how we reach step n-1, there’s only one way to reach n from here. The same holds true for n-2. We don’t really care how we got to either of these stepping stones, there is only one path is forward (to reach n). And each route that we took to get to either of these stepping stones is valid.

So essentially, the way we reach n would be-

ways(n)= ways(n-1) + ways(n-2)

Fun math problem- how would this change if you could take multiple paths to get to n from n-1/n-2? Or how would it change if you added more possible steps you could take at a time? Think about it and lmk. The hint for the former problem is in last week’s solution

Technology Made Simple

[Solution]Problem 55:Playlist with Buffer[Apple]

To learn more about the newsletter, check our detailed About Page + FAQs To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email. Recommend this publication to Substack over here…

3 years ago · 3 likes · Devansh

Okay, we have a recurrence relation and base cases. So we can get to coding? It shouldn’t be hard to implement DP on a relatively simple relation. I saw lots of solutions online just coding things up. We will do one final thing.

Step 4: Recognizing the Fibo

If you go to your interview, solve this relationship, and not are unable to recognize that this is the exact formulation for the Fibonacci series, God help you. I will find you and spray paint this function all over your house. If your mom wakes you up at 3 AM and asks you to recognize this formulation, you’d better get this right.

Here is why that is important here. One- it allows you to show off your knowledge. Two- You could mechanistically implement a Dynamic Programming solution by using a cache to store the number of ways. I saw a lot of solutions do this. But, if you know the code for generating Fibonacci numbers, you can attain the same results by using just 2 variables. You go from O(n) to O(1) space usage.

Let’s now look over the code. Because this is such an important function, make sure you really get this. On a spiritual level.

Step 5: Code (+ Fun Math Trivia)

The code looks like this. Should not surprise you. I used an additional base case because the sample outputs gave that to us. It honestly doesn’t make a huge difference if you do it the normal way.

class Solution:
    def climbStairs(self, n: int) -> int:
        if(n<=3):
            return n
        
        one,two=2,3 #minus_one, minus_two    
        for i in range(4,n+1):
            two = one + two
            one = two-one
        return two

Now for the fun math. Did you know that for very large n values, you can approximate them using the Golden Ratio? For very large successive values of the sequence, the values have a ratio approaching the Golden Ratio. This gives us a geometric sequence. We can thus approximate n=111000000000 directly, instead of having to generate the values. Pretty neat, huh? Will do a Math Monday on that if you’re interested. Meanwhile, make sure you flex this newfound knowledge at every possible avenue. So that bringing this up is in your muscle memory, when your interviewer asks you this question.

Time Complexity- O(N).

Space Complexity- O(1)

Loved the solution? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.