101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Dynamic Programming - Complex approach
  2. Space-Optimized Dynamic Programming - Complex approach
  3. Matrix Exponentiation - Complex approach

Approach 1: Dynamic Programming

The key insight for solving this problem is to recognize that it follows the Fibonacci sequence pattern.

Let's define dp[i] as the number of ways to reach the i-th step.

To reach the i-th step, we can either:

  • Take a single step from the (i-1)-th step, or
  • Take a double step from the (i-2)-th step

Therefore, the recurrence relation is:

dp[i] = dp[i-1] + dp[i-2]

The base cases are:

  • dp[1] = 1 (there is only one way to climb 1 step)
  • dp[2] = 2 (there are two ways to climb 2 steps: 1+1 or 2)

We can use a bottom-up approach to fill the DP array from the base cases up to n.

Algorithm:

  1. Create a DP array dp of size n+1.
  2. Set the base cases: dp[1] = 1 and dp[2] = 2.
  3. For i from 3 to n, compute dp[i] = dp[i-1] + dp[i-2].
  4. Return dp[n].

Time Complexity:

O(n)

We need to compute the number of ways for each step from 3 to n, which requires a constant amount of work for each step.

Space Complexity:

O(n)

We use a DP array of size n+1 to store the number of ways to reach each step.

Approach 2: Space-Optimized Dynamic Programming

Since we only need the previous two values to compute the current value, we can optimize the space complexity to O(1) by using just two variables instead of an array.

Let's define prev1 as the number of ways to reach the (i-1)-th step and prev2 as the number of ways to reach the (i-2)-th step.

Then, the number of ways to reach the i-th step is prev1 + prev2.

After computing this value, we update prev2 to prev1 and prev1 to the current value, and continue the iteration.

Algorithm:

  1. If n is 1, return 1.
  2. Initialize prev1 = 2 (ways to reach step 2) and prev2 = 1 (ways to reach step 1).
  3. For i from 3 to n:
  4. a. Compute current = prev1 + prev2.
  5. b. Update prev2 = prev1 and prev1 = current.
  6. Return prev1.

Time Complexity:

O(n)

We still need to iterate from 3 to n, performing constant work at each step.

Space Complexity:

O(1)

We only use two variables to store the previous two values, regardless of the input size.

Approach 3: Matrix Exponentiation

For larger values of n, we can use matrix exponentiation to compute the Fibonacci numbers more efficiently.

The Fibonacci sequence can be represented using a 2x2 matrix:

[1 1]n = [Fn+1 Fn]
[1 0] [Fn Fn-1]

By computing this matrix raised to the power of n-1, we can find the n-th Fibonacci number, which is the number of ways to climb n steps.

Matrix exponentiation can be done in O(log n) time using the binary exponentiation algorithm.

Algorithm:

  1. If n is 1, return 1.
  2. Define a 2x2 matrix base = [[1, 1], [1, 0]].
  3. Compute base^(n-1) using binary exponentiation.
  4. The result is in the top-left element of the resulting matrix.
  5. Return this value.

Time Complexity:

O(log n)

Using binary exponentiation, we can compute the matrix power in logarithmic time.

Space Complexity:

O(1)

We only use a constant amount of space to store the 2x2 matrices.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
function climbStairs(n):
    if n == 1:
        return 1
    
    dp = new array of size n+1
    dp[1] = 1
    dp[2] = 2
    
    for i from 3 to n:
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone