LeetCode Problem -2 (Climbing Stairs)

Climbing Stairs

Problem Statement :

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

Solution to above problem :

Imagine you are climbing a big staircase. Each time you can either take one step or two steps. The code helps you figure out how many different ways you can climb to the top of the staircase!

class Solution:
    def climbStairs(self, n: int) -> int:
        f = [1, 2, 3]
        if n <= 3:
            return f[n-1]

        for i in range(4, n+1):
            temp = f[i-2] + f[i-3]
            f.append(temp)

        return f[n-1]

Explanation:

• At the start, we have a list f with the numbers 1, 2, and 3. These numbers represent the ways to climb the first three steps.
• If you want to climb only 1, 2, or 3 steps, the code already knows the answer, and it gives you that answer directly.
• If you want to climb more than 3 steps, the code uses a loop to figure out the ways to climb each step based on the ways to climb the previous steps.
• It keeps adding new ways to the list f until it reaches the number of steps you want to climb.
• Finally, it tells you how many ways there are to climb to the top!

Complexities:

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

Why Not Use Recursion:

Using recursion for this problem can be less efficient because it might end up recalculating the same steps multiple times, making it slower. The dynamic programming approach used in this code avoids redundant calculations, making it more efficient for larger numbers of steps. Recursion can lead to a lot of repeated work, and in this case, it’s better to use a loop to keep track of the results efficiently.