Leetcode 70. Climbing Stairs

 70. Climbing Stairs

Easy, Dynamic Programming

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

The Climbing Stairs problem asks for the number of distinct ways to reach the top of a staircase with n steps, where you can climb either 1 or 2 steps at a time.

Approach 1: Dynamic Programming

Explanation:

We can solve this problem using dynamic programming. The key observation is that the number of ways to reach the n-th step can be computed by the sum of the ways to reach the (n-1)-th step and the (n-2)-th step, because from both of these steps, you can reach the n-th step by climbing 1 or 2 steps, respectively.

This gives us the recurrence relation:

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

Where:

• ways(0) = 1 (1 way to stay at the base without climbing any steps).
• ways(1) = 1 (1 way to reach the first step: a single 1-step move).

Steps:

1. Define dp[i] as the number of ways to reach the i-th step.
2. The number of ways to reach the i-th step is the sum of the number of ways to reach the (i-1)-th step and the (i-2)-th step.
3. Use the recurrence relation to fill in the values.

Code:

public class Solution {
    public int ClimbStairs(int n) {
        if (n == 1) return 1;
        
        int first = 1, second = 2;
        
        for (int i = 3; i <= n; i++) {
            int temp = second;
            second = first + second;
            first = temp;
        }
        
        return second;
    }
}

Explanation of the Code:

• If n == 1, the answer is 1 because there is only one way to climb 1 step.
• We initialize two variables first = 1 and second = 2 to represent the number of ways to reach step 1 and step 2, respectively.
• For each step from 3 to n, we compute the number of ways to reach the step using the recurrence relation second = first + second and update first to the previous value of second.
• Finally, we return second, which holds the number of ways to reach the n-th step.

Time and Space Complexity:

• Time Complexity: $O(n)$ because we loop through the steps once.
• Space Complexity: $O(1)$ since we are using only a few variables to store intermediate results, regardless of the size of n.

---

Approach 2: Optimized Space (Using Two Variables)

Instead of maintaining an entire DP array, we can optimize space by keeping track of only the last two values (first and second), as each value depends only on the previous two.

Code (same as above):

The previous code already optimizes space using only two variables (first and second), so the space complexity is already optimized.

Time Complexity:

• Time Complexity: $O(n)$, as we still loop through n steps.
• Space Complexity: $O(1)$, using only constant space.

---

Approach 3: Recursive Solution (with Memoization)

Another approach is to use recursion with memoization. The idea is to break the problem into subproblems and store the results to avoid redundant calculations.

Code:

public class Solution {
    public int ClimbStairs(int n) {
        Dictionary<int, int> memo = new Dictionary<int, int>();
        return Helper(n, memo);
    }
    
    private int Helper(int n, Dictionary<int, int> memo) {
        if (n <= 1) return 1;
        if (memo.ContainsKey(n)) return memo[n];
        
        memo[n] = Helper(n - 1, memo) + Helper(n - 2, memo);
        return memo[n];
    }
}

Explanation:

• We use a helper function Helper that recursively calculates the number of ways to reach step n.
• The results of previous subproblems are stored in a memo dictionary to avoid redundant calculations.
• Base case: If n is 0 or 1, return 1 because there’s only one way to reach the top.
• The function calculates Helper(n-1) + Helper(n-2) for each n and stores the result in the memo dictionary.

Time and Space Complexity:

• Time Complexity: $O(n)$, due to memoization.
• Space Complexity: $O(n)$, due to the recursion stack and memoization dictionary.

---

Summary:

Approach	Time Complexity	Space Complexity	Explanation
Dynamic Programming (Tabulation)	$O(n)$	$O(1)$	Efficient iterative solution using two variables.
Recursive with Memoization	$O(n)$	$O(n)$	Recursive solution with memoization to avoid repeats.
Dynamic Programming (Full Array)	$O(n)$	$O(n)$	Uses a full DP array (less space efficient).

---

The dynamic programming solution is the most efficient and commonly used approach, especially with the space optimization to use only two variables.