Topic · 1D Dynamic ProgrammingEasy ~15 min to read and practice

Climbing Stairs

Understand the problem

You're climbing a staircase with n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you reach step n?

Example:

n = 2
output = 2  // [1+1] or [2]

n = 3
output = 3  // [1+1+1], [1+2], [2+1]

Observation: the number of ways to reach step n = the number of ways to reach step n-1 (then take 1 step) + the number of ways to reach step n-2 (then take 2 steps).

That's exactly the Fibonacci recurrence — the intro problem of 1D dynamic programming (DP-1D).

Show the basic approach (slower)

Basic approachO(2ⁿ) time, O(n) space (call stack)

function climbStairs(n: number): number {
  // Plain recursion — each call branches into 2 subcalls
  if (n <= 1) return 1
  return climbStairs(n - 1) + climbStairs(n - 2)
}

Why this approach is slow:

The recursion tree branches twice at every node and is n levels deep → O(2ⁿ) calls.

Many subproblems are recomputed again and again — that's why you need dynamic programming.

Optimal solution

OptimalO(n) time, O(n) space

function climbStairs(n: number): number {
  if (n <= 1) return 1
  const dp = new Array<number>(n + 1)
  dp[0] = 1  // 1 way to stand on step 0 (no climbing)
  dp[1] = 1  // 1 way to reach step 1
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]  // recurrence relation
  }
  return dp[n]
}

Key insight:

Store each step's result in a dp array so nothing is recomputed.

Each dp[i] only needs the previous 2 values — you can optimize further to O(1) space with 2 variables instead of a whole array.

Step-by-step trace

Step through the run — click a step to see its line of code

1function climbStairs(n: number): number {
2  if (n <= 1) return 1
3  const dp = new Array<number>(n + 1)
4  dp[0] = 1  // 1 way to stand on step 0 (no climbing)
5  dp[1] = 1  // 1 way to reach step 1
6  for (let i = 2; i <= n; i++) {
7    dp[i] = dp[i - 1] + dp[i - 2]  // recurrence relation
8  }
9  return dp[n]
10}

Edge cases to remember

n=0 — already at the destination, 1 way (don't climb).
n=1 — exactly 1 way: take 1 step.
Large n (e.g. n=45) — the result is the 46th Fibonacci number (1,836,311,903), still within JavaScript's safe integer range (~2⁵³).
Space optimization: replace dp[] with 2 variables prev and curr, cutting O(n) space down to O(1).

Related interview questions

Dynamic programming (DP) applies when the problem has:
1. Overlapping sub-problems — the same sub-problem is solved many times
2. Optimal substructure — the optimal answer to the whole is built from optimal answers to the parts

With only (1) you need memoization. With both, DP is the right call.

1D DP = the state needs a single index (i). A dp[] array holds the result at each position.

General pattern:

const dp = new Array(n).fill(0)
dp[0] = base case
for (let i = 1; i < n; i++) {
  dp[i] = f(dp[i-1], dp[i-2], ...)  // transition
}
return dp[n-1]

Classic examples:
- Fibonacci: dp[i] = dp[i-1] + dp[i-2]
- Climbing Stairs: dp[i] = dp[i-1] + dp[i-2]
- House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
- Maximum Subarray (Kadane): dp[i] = max(nums[i], dp[i-1] + nums[i])

Tip: most 1D DP only reads the last two values (prev, curr) → space optimizes down to O(1).

Top missed: empty input, single element, all duplicates, sorted/reverse-sorted, negatives, overflow, null pointers, off-by-one, cycles in graphs.

Always clarify constraints upfront and write tests proving the handling.

8-step flow: restate, clarify constraints, brute force baseline, identify bottleneck, propose optimal pattern, code clearly, dry-run, test edge cases + Big-O.

Avoid silence, premature optimization, and ignoring edges.
Reasoning matters more than memorized solutions.

function climbStairs(n: number): number {
  if (n <= 1) return 1
  const dp = new Array<number>(n + 1)
  dp[0] = 1  // 1 way to stand on step 0 (no climbing)
  dp[1] = 1  // 1 way to reach step 1
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]  // recurrence relation
  }
  return dp[n]
}

Key insight:

Store each step's result in a dp array so nothing is recomputed.

Each dp[i] only needs the previous 2 values — you can optimize further to O(1) space with 2 variables instead of a whole array.

Step-by-step trace

Step through the run — click a step to see its line of code

1function climbStairs(n: number): number {
2  if (n <= 1) return 1
3  const dp = new Array<number>(n + 1)
4  dp[0] = 1  // 1 way to stand on step 0 (no climbing)
5  dp[1] = 1  // 1 way to reach step 1
6  for (let i = 2; i <= n; i++) {
7    dp[i] = dp[i - 1] + dp[i - 2]  // recurrence relation
8  }
9  return dp[n]
10}

Edge cases to remember

n=0 — already at the destination, 1 way (don't climb).

n=1 — exactly 1 way: take 1 step.

Large n (e.g. n=45) — the result is the 46th Fibonacci number (1,836,311,903), still within JavaScript's safe integer range (~2⁵³).

Space optimization: replace dp[] with 2 variables prev and curr, cutting O(n) space down to O(1).

Climbing Stairs

Understand the problem

Optimal solution

Step-by-step trace

Edge cases to remember

Further reading

Climbing Stairs

Understand the problem

Optimal solution

Step-by-step trace

Edge cases to remember

Further reading

Understand the problem

Optimal solution

Step-by-step trace

Edge cases to remember

Related interview questions

Further reading

Same-topic problems

House Robber

Longest Increasing Subsequence

Word Break

Understand the problem

Optimal solution

Step-by-step trace

Edge cases to remember

Related interview questions

Further reading

Same-topic problems

House Robber

Longest Increasing Subsequence

Word Break