Problem 28 - Climbing Stairs

Explore our archive for previous posts.

Question

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

Approach

The problem can be solved using dynamic programming. The goal is to find the number of distinct ways to climb to the top of a staircase with 'n' steps. At each step, a person can climb either 1 or 2 steps.

Let's consider the steps needed to reach the current step 'i'. A person can either come from step 'i-1' (taking one step) or from step 'i-2' (taking two steps) to reach step 'i'. So, the total number of distinct ways to reach step 'i' is the sum of the ways to reach step 'i-1' and step 'i-2'.

By building the dynamic programming array dp from the base cases (dp[1] = 1 and dp[2] = 2) and applying the recursive relation for each subsequent step, we can efficiently calculate the number of distinct ways to climb to the top of the staircase with 'n' steps.

Solution

Solve it here

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n; // Base cases: for n = 1, return 1; for n = 2, return 2
        }
        
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        
        for (int i = 3; i <= n; i++) {
            // We can reach step 'i' from 'i - 1' or 'i - 2'
            dp[i] = dp[i - 1] + dp[i - 2]; 
        }
        
        // Return the number of ways to reach the top
        return dp[n];
    }
}

Time and space complexity

Time Complexity: The time complexity is O(n), where 'n' is the number of steps. The algorithm iterates through the loop 'n' times to populate the dynamic programming array dp. Since each iteration takes constant time, the overall time complexity is linear in terms of the number of steps.

Space Complexity: The space complexity is O(n) as we use a dynamic programming array dp of size n+1 to store the results for each step. As the size of the array grows linearly with the number of steps, the space complexity is proportional to 'n'.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!