TIC
The Interns Company

Climbing Stairs

EasyAcceptance: 49.8%
MathDynamic ProgrammingMemoization

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?

Constraints:

  • 1 <= n <= 45

Input Format:

  • An integer n, representing the number of steps in the staircase

Output Format:

  • Return the number of distinct ways to climb to the top

Examples:

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

Example 3:

Input:

n = 4

Output:

5

Explanation:

There are five ways to climb to the top. 1. 1 + 1 + 1 + 1 2. 1 + 1 + 2 3. 1 + 2 + 1 4. 2 + 1 + 1 5. 2 + 2

Solutions

Dynamic Programming

Time: O(n)
Space: O(n)

Use a bottom-up approach to build the solution. Define dp[i] as the number of ways to reach step i. Then dp[i] = dp[i-1] + dp[i-2].

Space-Optimized Dynamic Programming

Time: O(n)
Space: O(1)

Since we only need the previous two values to calculate the current value, we can optimize space by using only two variables instead of an array.

Fibonacci Formula

Time: O(log n)
Space: O(1)

The climbing stairs problem is equivalent to finding the (n+1)th Fibonacci number. We can use the mathematical formula to calculate it directly.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Initialize the dp array: dp = [0, 1, 2, ?, ?, ?]
  2. Calculate dp[3] = dp[2] + dp[1] = 2 + 1 = 3
  3. Calculate dp[4] = dp[3] + dp[2] = 3 + 2 = 5
  4. Calculate dp[5] = dp[4] + dp[3] = 5 + 3 = 8
  5. Return dp[5] = 8

Hints

Hint 1
Try to think of the problem in terms of recurrence relation. How can you express the number of ways to reach step n in terms of previous steps?
Hint 2
Notice that to reach step n, you can either take a single step from step n-1 or take two steps from step n-2.
Hint 3
The number of ways to reach step n is the sum of the number of ways to reach step n-1 and step n-2.

Video Tutorial

Climbing Stairs - Dynamic Programming

YouTube•Learn the Climbing Stairs solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize how the number of ways to climb the stairs follows the Fibonacci sequence, where each value is the sum of the two previous values.

Key visualization elements:

  • current step
  • ways count
  • fibonacci pattern

Asked By

AmazonMicrosoftGoogleAppleAdobeFacebookUber

Implementation Notes

This problem is a classic example of dynamic programming where we can optimize our approach from recursion to iteration, and then optimize space complexity. It's also a great introduction to Fibonacci numbers and their properties.