Climbing Stairs easy

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

Steps to Solve

This problem can be solved using dynamic programming. The key observation is that to reach step n, you must have come from either step n-1 or step n-2. Therefore, the number of ways to reach step n is the sum of the number of ways to reach step n-1 and the number of ways to reach step n-2.

We can represent this recursively, but a dynamic programming approach (iterative) is more efficient to avoid redundant calculations.

1. Base Cases:

   • If n = 1, there's only 1 way (one step).
   • If n = 2, there are 2 ways (two single steps or one double step).

2. Iteration:

   • Create an array dp of size n + 1 to store the number of ways to reach each step. Initialize dp[1] = 1 and dp[2] = 2.
   • Iterate from i = 3 to n. For each step i, calculate dp[i] = dp[i-1] + dp[i-2].

3. Return:

   • Return dp[n], which represents the number of ways to reach the nth step.

Explanation

The dynamic programming approach efficiently calculates the number of ways to reach each step. By building up from the base cases (1 and 2 steps), we avoid recalculating the number of ways for previously computed steps. This iterative approach has a time complexity linear in n.

Code (C++)

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

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

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

        return dp[n];
    }
};

Complexity

• Time Complexity: O(n) - The loop iterates through n steps.
• Space Complexity: O(n) - The dp array stores n values. This can be optimized to O(1) by only storing the last two values. See optimized code below.

Optimized Code (C++) - O(1) Space Complexity

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

        int prev1 = 1;
        int prev2 = 2;
        int current;

        for (int i = 3; i <= n; ++i) {
            current = prev1 + prev2;
            prev1 = prev2;
            prev2 = current;
        }

        return prev2;
    }
};

This optimized version achieves the same result while only using constant extra space. It keeps track of only the last two computed values (prev1 and prev2) instead of storing the entire array.