Coding Interview PatternsClimbing Stairs
EasyDynamic Programming

Climbing Stairs

Explanation & Solution

Practice Problem

Description

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. Return the number of distinct ways you can climb to the top.

Input: n = 2

Output: 2

Explanation: There are two ways to climb to the top: 1 + 1 and 2.

Constraints

  • 1 <= n <= 45

Approach

Dynamic Programming pattern

1. Identify the Recurrence

  • To reach step i, you can come from step i - 1 (one step) or step i - 2 (two steps)
  • Therefore dp[i] = dp[i - 1] + dp[i - 2]
  • This is the Fibonacci recurrence

2. Establish Base Cases

  • dp[1] = 1 — there is exactly one way to reach step 1 (take one step)
  • dp[2] = 2 — there are two ways to reach step 2 (1+1 or 2)

3. Optimize Space

  • We only need the previous two values at any time
  • Use two variables prev2 and prev1 instead of a full array
  • Iterate from step 3 to n, updating both variables each iteration

4. Return the Result

  • After the loop, prev1 holds the number of distinct ways to reach step n

Key Insight

  • This problem is equivalent to computing the n-th Fibonacci number
Time
O(n)single pass from 3 to n
Space
O(1)only two variables maintained

Visualization

Input:
Dynamic Programmingn = 2
dp
—0—1—2

Press play to start DP animation

ComputingDependencyFilledEmpty
4 steps

Solution Code

Next
House Robber