easy

Climbing Stairs

Count how many distinct ways you can climb a staircase taking one or two steps at a time.

1. Define the problem

Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top. Each time you can climb either 1 or 2 steps. Return the number of distinct ways you can climb to the top. The number of ways to reach step i has optimal substructure : it is exactly the ways to reach step i-1 plus the ways to reach step i-2, two smaller subproblems that keep getting asked for again. Cache each step as you compute it and build the table bottom-up from step 1 to step n.

Constraints

  • 1 ≤ n ≤ 45

Example

Inputn = 5
Output8

Explanation ways(5) = ways(4) + ways(3) = 5 + 3 = 8, reusing the two answers computed right before it.

2. Know the words first

In plain terms

Subproblem
A smaller version of the same question — here, "how many ways to reach an earlier step?"
3. Visualize the solution

Build the ways table from step 1 up to step n

Build the ways table from step 1 up to step n
Statusbase

The whole table for n = 5 is laid out. dp[1] = 1 and dp[2] = 2 are the base cases; the rest are still empty.

What happens in this step

dp[1] = 1   (the only way: one single step)
dp[2] = 2   (two single steps, or one double step)

Every cell from dp[3] to dp[5] is still blank because it has not been worked out yet. These two base cases seed all of them.
Step 1 of 5

Steps to visualize

  1. Set the base cases: ways(1) = 1 and ways(2) = 2.
  2. For every step i from 3 to n, set ways(i) = ways(i-1) + ways(i-2).
  3. Each new step reuses the two cells directly before it instead of recomputing them.
  4. The value at step n is the answer.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Build the ways table from step 1 up to step n
Statusbase

The whole table for n = 5 is laid out. dp[1] = 1 and dp[2] = 2 are the base cases; the rest are still empty.

What happens in this step

dp[1] = 1   (the only way: one single step)
dp[2] = 2   (two single steps, or one double step)

Every cell from dp[3] to dp[5] is still blank because it has not been worked out yet. These two base cases seed all of them.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function climbStairs(n) {
  if (n <= 2) return n;

  let prev2 = 1;
  let prev1 = 2;

  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }

  return prev1;
}
Time
O(n)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
n = 58example from the docstring
n = 22boundary base case, two steps
n = 11smallest valid input, a single step
n = 33first step that combines both base cases
n = 1089several steps of accumulation
n = 451836311903upper bound of the constraint range

Keep reading