· By John Kavanagh

Climbing Stairs in TypeScript: Where the Recurrence Comes from

Uneven stone steps climbing a leafy woodland path.
Image by Bobby Iv, licensed from Unsplash.

Climbing Stairs is often introduced as a Fibonacci question. That is a convenient answer if you already know why the sequence appears, and rather less helpful if the recurrence is the bit you are trying to learn.

I prefer to leave Fibonacci out of the opening calculation. Start with the last move instead. If you can climb one or two steps at a time, where could you have been immediately before reaching the top? Answer that carefully and the recurrence follows without needing to recognise a famous sequence on sight.

LeetCode's Climbing Stairs problem asks for the number of distinct routes to step n. Order matters: taking one step and then two is different from taking two and then one. We are counting sequences of moves, not choosing a bag of step sizes.


Separate Routes by Their Last Move

Let ways[i] count the routes that land exactly on step i. Every route to that step ends with either a one‑step move from i - 1 or a two‑step move from i - 2.

Those two groups do not overlap, because a route has only one final move. They also cover every legal route, because no other move size is allowed. Appending the final move gives a one‑to‑one correspondence with routes to the earlier step.

So the number of routes is ways[i - 1] + ways[i - 2]. That is the reasoning behind the addition. The code should record it, rather than asking the reader to trust that adding two previous values is something dynamic programming generally likes to do.

For four steps, the five routes are:

  • 1 + 1 + 1 + 1
  • 1 + 1 + 2
  • 1 + 2 + 1
  • 2 + 1 + 1
  • 2 + 2

The routes ending in one come from the three routes to step three. The routes ending in two come from the two routes to step two. Three plus two gives five, without generating the five sequences in the implementation.


Why the Empty Route Counts Once

There is one route to step zero: make no moves. That gives ways[0] = 1. There is also one route to step one: take one step, so ways[1] = 1.

The zero value can feel like a trick until you apply it to step two. We need to count the route consisting of a single two‑step move. It extends the empty route, so it contributes one. Initialising ways[0] to zero would remove that route and every larger route that depends on it.

The challenge itself starts at n = 1. Step zero is a subproblem we introduce to describe the starting position. We do not need to invent a special input convention to justify it, and these examples do not promise to validate arbitrary negative or fractional values.

The first few values are useful to write down before reaching for code:

StepRoutesExplanation
01The empty route
11One single step
22One plus one, or two
33Two routes from step two, one from step one
45Three routes from step three, two from step two
58Five routes from step four, three from step three

Keep the Earlier Answers in a Table

The table version makes the correspondence between the definition and the implementation quite direct.

const climbStairs = (n: number): number => {
  const ways = Array<number>(n + 1).fill(0);
  ways[0] = 1;
  ways[1] = 1;

  for (let step = 2; step <= n; step += 1) {
    ways[step] = ways[step - 1] + ways[step - 2];
  }

  return ways[n];
};

By the time an iteration starts, both earlier counts have already been calculated. Each step is processed once, so the running time is O(n). The array contains n + 1 numbers, giving O(n) auxiliary space.

A recursive version can express the same recurrence, but a plain recursive implementation calculates the same smaller answers repeatedly. Expanding the calls quickly reveals overlapping branches. Memoisation would avoid that repetition, although it still keeps stored results and a call stack. For this particular dependency chain, the loop is simpler to inspect.

The table is also useful if you need counts for several smaller staircase lengths after calculating a maximum. Saving all the values is then a feature. Optimising storage before deciding what the caller needs can leave you doing the same work twice.


Two Counters are Enough for One Answer

For a single target, only the previous two values remain useful. The rest of the table can disappear.

const climbStairs = (n: number): number => {
  let twoBack = 1;
  let oneBack = 1;

  for (let step = 2; step <= n; step += 1) {
    const current = oneBack + twoBack;
    twoBack = oneBack;
    oneBack = current;
  }

  return oneBack;
};

At the start of the loop for step i, twoBack holds ways[i - 2] and oneBack holds ways[i - 1]. We calculate the new count before shifting either previous value. After the assignments, the same statement will be true for the next iteration.

That invariant is short enough to say aloud, which is usually a good sign. Updating twoBack first and then adding it to oneBack would accidentally add the same previous value twice. I would rather keep the extra current variable than save a line and hide the mistake.

The rolling version still takes O(n) time and now uses O(1) auxiliary space within the challenge's numeric limits. For n = 1, the loop does not run and the initial answer is already correct.


Check the Count with a Different Argument

I want more than two implementations agreeing, because they could share the same mistake. There is another way to count a route: choose how many two‑step moves it contains.

If there are k two‑step moves, the remaining distance needs n - 2k one‑step moves. That makes n - k moves altogether. Choose which k of those positions contain a two‑step move, then sum across all possible values of k.

For four steps, zero two‑step moves gives one arrangement. One two‑step move gives three arrangements. Two two‑step moves gives one arrangement. The total is five again, now reached through combinations of positions rather than the recurrence.

My Dynamic Programming Comparison Lab uses exact binomial arithmetic to check every permitted input from one to 45. It also enumerates short routes and demonstrates an incorrect implementation that counts combinations instead of sequences. This gives you a small failure to inspect when loop order feels arbitrary.


Know Which Question the Numbers Answer

The official maximum is 45 steps. Its answer, 1,836,311,903, is exactly representable as a JavaScript number. Extending the function indefinitely would eventually exceed the safe‑integer range, even though JavaScript would continue returning a number. If you lift the constraints, consider BigInt and include the growing integer size in any complexity discussion.

Changing the permitted moves changes the recurrence. Adding a three‑step move adds a predecessor. Blocking a step makes its count zero. Adding a cost changes the question from counting routes to finding a minimum, so blindly reusing the addition would be wrong.

My Unique Paths article uses the same habit of counting disjoint ways to arrive, this time on a grid. My guide to choosing dynamic‑programming state develops the broader question: what does one saved answer need to tell the next calculation?

For Climbing Stairs, the saved answer is deliberately small. Count the routes to one step, justify the starting values, and make sure the two possible final moves cover everything exactly once. Recognising Fibonacci is a useful observation afterwards. It needn't be the admission ticket.

Downloadable Resource

  • Dynamic Programming Comparison Lab

    Run my fourteen TypeScript solutions across seven problems, with independent checks for string edits, decoding counts, staircase routes, prefixes, and subsequences.

    Download ZIP

Want to find out more?

If you need senior hands‑on support with a complex React or Next.js platform, migration, performance issue, or technical SEO problem, send me the context and I'll tell you where I can help.