DSA Patterns for Coding Interviews: The Techniques Behind Almost Every Problem

Dynamic Programming Part 1

A problem is a dynamic-programming problem when it has both of two properties, and it's worth checking for both explicitly rather than pattern-matching on vibes: overlapping subproblems — a straightforward recursive solution ends up calling itself with the exact same arguments over and over — and optimal substructure — the optimal answer to the whole problem can be assembled directly from optimal answers to its subproblems. Overlapping subproblems alone just means plain recursion is slow; optimal substructure alone, without overlap, usually means ordinary divide-and-conquer already handles it fine without needing to cache anything.

Naive recursive Fibonacci from the complexity chapter is the textbook case of overlap: computing fib(5) recomputes fib(3) twice and fib(2) three times, and that duplication compounds exponentially as n grows.

Memoization (top-down)

function fibMemo(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);        // this exact subproblem was already solved
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

Still written as ordinary top-down recursion, but a cache keyed on the arguments means every distinct subproblem is computed exactly once — O(2ⁿ) collapses to O(n).

Tabulation (bottom-up)

function fibTab(n) {
  if (n <= 1) return n;
  const dp = new Array(n + 1);
  dp[0] = 0;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];             // build up from the smallest subproblems first
  }
  return dp[n];
}

Memoization only ever computes the subproblems actually demanded by the recursion, which can be a real win when the reachable subproblem space is sparse; tabulation avoids recursion's call-stack depth and overhead entirely, and its explicit iteration order tends to make a follow-up space optimization (below) much easier to see.

Walking through a 1D DP example: climbing stairs

The problem: count the number of distinct ways to climb n stairs, taking either 1 or 2 steps at a time.

Define the state first, in words, before writing any code: dp[i] = the number of distinct ways to reach step i. The transition follows directly from asking "what was the last step taken to arrive at i": it was either a single step from i - 1, or a double step from i - 2 — so dp[i] = dp[i - 1] + dp[i - 2].

function climbStairs(n) {
  const dp = new Array(n + 1);
  dp[0] = 1;                                    // one way to "climb" zero stairs: do nothing
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];               // arrived via a 1-step or a 2-step
  }
  return dp[n];
}

Trace it for n = 4: dp[0..4] fills in as 1, 1, 2, 3, 5 — each value built purely from the two before it, and the final answer, 5, is exactly the count of every way to sequence 1s and 2s that sum to 4.

Notice that dp[i] only ever reads the two most recent entries, never anything further back — which means the whole array can collapse down to two rolling variables, dropping the space from O(n) to O(1):

function climbStairsOptimized(n) {
  let prev2 = 1, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    [prev2, prev1] = [prev1, prev1 + prev2];
  }
  return prev1;
}

This rolling-variable trick is worth reaching for any time a 1D DP's transition only looks a fixed, small number of steps backward — it's a mechanical simplification once the array-based version is already correct, not a separate technique to learn from scratch.

Practice this on Code Lab: Dynamic Programming