Memoisation versus tabulation

Top-down: memoised recursion

Write the recursion naturally, cache what it returns.

function climbStairs(n, memo = new Map()) {
  if (n <= 2) return n;
  if (memo.has(n)) return memo.get(n);

  const ways = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
  memo.set(n, ways);
  return ways;
}

Advantages: follows the problem statement directly, and only computes states it actually needs — which matters when the state space is large but sparsely reached.

Costs: call-stack depth, and function-call overhead per state.

Bottom-up: tabulation

Fill a table in dependency order, smallest first.

function climbStairsTable(n) {
  if (n <= 2) return n;

  const ways = new Array(n + 1);
  ways[1] = 1;
  ways[2] = 2;

  for (let i = 3; i <= n; i++) ways[i] = ways[i - 1] + ways[i - 2];

  return ways[n];
}

Advantages: no recursion, no stack limit, and the loop order makes space optimisation obvious.

Costs: you must work out the correct fill order yourself, and you compute every state whether it is needed or not.

Rolling the space down

Once tabulated, look at how far back the recurrence reaches. Climbing stairs only ever looks two rows behind:

function climbStairsRolling(n) {
  let prev = 1;
  let current = 2;

  for (let i = 3; i <= n; i++) [prev, current] = [current, prev + current];

  return n <= 2 ? n : current;
}

O(n) time, O(1) space. The same trick turns most 2D tables into two rows, or sometimes one — the standard follow-up after you produce a working DP.

Which to write

Start top-down. The recursion mirrors the problem, so it is easier to get right under pressure, and adding a memo is mechanical. Convert to tabulation when recursion depth is a risk or when the interviewer asks for the space optimisation.

Say this out loud: "I will write the recursion first, add memoisation, then convert to a bottom-up table and roll the space to O(n)." That sentence is a roadmap, and it earns credit before you have written a line.