The Problem:

In this problem, we are given a number 'n' which represents a flight of stairs. Our goal is to find the number of distinct ways the flight of stairs can be climbed given we can climb 1 or skip a stair and climb 2 steps at once.

Before we begin trying to figure out a solution for this problem, let’s first revisit an important concept: Recursion.

Understanding Recursion:

Recursion is essentially a function calling itself. It is frequently used to solve problems that can be divided into smaller, similar sub-problems and can be very useful in dynamic programming. To understand recursion, it can be helpful to break it down into 3 parts:

1. Base Condition: This condition prevents the recursive function from calling itself infinitely.
2. Recursive Call: This is responsible for calling the recursive function itself.
3. Small Calculation: This step, which can come before or after the Recursive Call, is responsible for performing some calculation that we need for the recursive function or for returning some result after a recursive call has been completed.

A recursive tree is a visual representation of the recursive calls made by a function. It can be very helpful in understanding how recursion works and in analyzing the time and space complexity of recursive algorithms.

Intuition:

With an understanding of how recursion works, let’s try to break down the problem. From the problem statement, we can deduce that if we are on stair 3, then the total number of ways to reach stair 3 would be the total number of ways to reach step 2 plus the total number of ways to reach step 1.

Step 2 can be reached in two ways:

1. By skipping step 1 and landing directly on step 2.
2. By not skipping any steps and climbing from step 1 to step 2.

The image below shows this in visual representation.

Since we know the answer to number of ways to reach step 2 and step 1 let them be the base case, with that in mind we can work out the following recursion tree.

Summary of Solution

Use recursion to find the number of ways to reach each step. The total number of ways to reach step n is the sum of the number of ways to reach step n-1 and step n-2. Use memoization to store the results and reduce time complexity from O(2^n) to O(n). The space complexity is O(n).

Code

This can be translated to code in the following way:

class Solution:
    def climbStairs(self, n: int) -> int:
        def f(n):
            if (n == 1 or n == 2):
                return n
            recursiveCall1 = f(n-1)
            recursiveCall2 = f(n -2)
            smallCalculation = recursiveCall1 + recursiveCall2
            return smallCalculation
        return f(n)

• Space Complexity O(n)
• Time Complexity O(2^n)

This code performs multiple calculations again and again, It will make 2 recursive calls every time. Therefore, the time complexity is O(2^n) hence on running this, one might get a time-out error. To solve this issue, we can introduce a temporary cache to hold values of our calculations and set another base case to search the cache. This is called memoization. The following code implements this technique:

class Solution:
    def climbStairs(self, n: int) -> int:
        memoise = {}
        def f(n):
            if (n == 1 or n == 2):
                return n
            if n in memoise:
                return memoise[n]
            recursiveCall1 = f(n-1)
            recursiveCall2 = f(n -2)
            smallCalculation = recursiveCall1 + recursiveCall2
            memoise[n] = smallCalculation
            return smallCalculation
        return f(n)

• Space Complexity O(n)
• Time Complexity O(n)

The time complexity is reduced as we are storing the results in a cache, If the function is called again with the same 'n' it will simply look up the cache and return the calculation, ensuring that function is called on 'n' just once.

This approach is simple and efficient, making it a good solution to this problem.

I hope you enjoyed this post. Stay tuned for daily LeetCode blog posts!