Climbing Stairs 🧠

LeetCode Link: Climbing Stairs

Difficulty: Easy

Problem Explanation 📝

Problem: LeetCode 70 - Climbing Stairs

Description: You are climbing a staircase that has n steps. You can either climb 1 or 2 steps at a time. Return the number of distinct ways to climb to the top.

Intuition: To reach the nth step, we can either take a single step from the (n-1)th step or take two steps from the (n-2)th step. This forms the basis of our dynamic programming approach, as we can break down the problem into subproblems and build the solution from there.

Approach:

1. Initialize an array dp of size (n+1) to store the number of distinct ways to reach each step.
2. Set the base cases: dp[0] = 1 (no steps needed) and dp[1] = 1 (one step to reach the first step).
3. Iterate from 2 to n:

• Compute dp[i] by summing up the number of ways to reach the previous two steps: dp[i] = dp[i-1] + dp[i-2].

4. Return dp[n], which represents the number of distinct ways to reach the top step.

⌛ Time Complexity: The time complexity is O(n) since we iterate through the steps once.

💾 Space Complexity: The space complexity is O(n) since we use an array of size (n+1) to store the intermediate results.

Dynamic Programming:

• Subproblem: The subproblem is finding the number of distinct ways to reach the current step.
• Recurrence Relation: dp[i] = dp[i-1] + dp[i-2], where dp[i] represents the number of distinct ways to reach the ith step.
• Base Case: dp[0] = 1 and dp[1] = 1, as there is only one way to reach the first two steps.

Solutions 💡

Cpp 💻

class Solution {
  public:
    int climbStairs(int n) {
        if (n <= 2) {
            return n;  // Base cases
        }

        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];  // Recurrence relation
        }

        return dp[n];
    }
};

// O(1) Space
// class Solution {
// public:
//     int climbStairs(int n) {
//         if(n <= 2)
//             return n;

//         int first = 1, second = 2;

//         for(int  i = 2; i < n; i++) {
//             int temp = second;
//             second = first + second;
//             first = temp;
//         }
//         return second;
//     }
// };

Python 🐍

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        prev1 = 1  # Number of ways to reach the 1st stair
        prev2 = 2  # Number of ways to reach the 2nd stair

        for i in range(3, n + 1):
            current = prev1 + prev2
            prev1, prev2 = prev2, current  # Update for the next iteration

        return prev2  # Number of ways to reach the n-th stair