algoadvance

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:

Clarifying Questions

  1. Is the order of steps taken important? Yes, the order in which steps are taken is important. For example, taking steps like 1 + 2 is different from 2 + 1.

  2. Do we always start at step 0? Yes, you start from step 0.

  3. Can we assume the input will always be an integer within the given range? Yes, the input n is always an integer within the range [1, 45].

Strategy

This problem can be solved using dynamic programming. The main idea is similar to the Fibonacci sequence approach because from any step i, you can either come from step i-1 or step i-2.

Let dp[i] represent the number of ways to reach step i. The recurrence relation is: [ dp[i] = dp[i-1] + dp[i-2] ]

Where:

We will compute dp values from 3 to n and return dp[n].

Time Complexity

The time complexity of this solution is (O(n)) because we compute the number of ways to each step only once.

The space complexity is (O(n)) because of the extra space used for the dp array, but it can be optimized to (O(1)) if only the last two computed values are kept.

Code

def climbStairs(n: int) -> int:
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

# Test cases
print(climbStairs(2))  # Output: 2
print(climbStairs(3))  # Output: 3
print(climbStairs(4))  # Output: 5

Alternatively, we can optimize the space complexity to (O(1)):

def climbStairs(n: int) -> int:
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    a, b = 1, 2
    
    for i in range(3, n + 1):
        a, b = b, a + b
    
    return b

# Test cases
print(climbStairs(2))  # Output: 2
print(climbStairs(3))  # Output: 3
print(climbStairs(4))  # Output: 5

This optimized approach maintains two variables to track the previous two values which saves on space while maintaining the linear time complexity.

Try our interview co-pilot at AlgoAdvance.com