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

Part 11 of 16 · ~3 min

Dynamic Programming Part 1

Two properties, both required, worth checking explicitly rather than guessing: overlapping subproblems — plain recursion ends up solving the exact same smaller case more than once — and optimal substructure — the best whole-problem answer can be built directly from the best answers to its pieces. Have overlap without optimal substructure and the fix is simply speeding up slow recursion; have optimal substructure without any real overlap and a plain divide-and-conquer approach was already the right tool, with no cache required.

Remember the O(2ⁿ) row from the Big-O table a few chapters back? Here it is for real. This term's electives only come in two sizes — 3 credits and 4 — and an advisor wants to know how many distinct sequences of them, one per semester, land on an exact target total. The straightforward recursive answer:

function waysToReachCreditsNaive(target) {
  if (target === 0) return 1;             // one way to reach zero: take nothing else
  if (target < 0) return 0;               // overshot — not a valid sequence
  return waysToReachCreditsNaive(target - 3) + waysToReachCreditsNaive(target - 4);
}

Correct, and disastrously slow past a modest target — the same reason naive Fibonacci falls apart. waysToReachCreditsNaive(10) ends up calling waysToReachCreditsNaive(6) through more than one branch of its own recursion, redoing work it already did somewhere else in the tree. That repetition compounds fast as the target climbs.

Memoization (top-down)

function waysToReachCredits(target, memo = new Map()) {
  if (target === 0) return 1;
  if (target < 0) return 0;
  if (memo.has(target)) return memo.get(target);        // already solved this one
  const ways = waysToReachCredits(target - 3, memo) + waysToReachCredits(target - 4, memo);
  memo.set(target, ways);
  return ways;
}

Still ordinary top-down recursion at heart — the only addition is a cache indexed by the argument, so a subproblem that's already been solved gets handed back instantly instead of recomputed. That single change is enough to bring the exponential blowup down to O(n).

Tabulation (bottom-up), and a hand trace

function waysToReachCreditsTab(target) {
  const dp = new Array(target + 1).fill(0);
  dp[0] = 1;
  for (let i = 1; i <= target; i++) {
    if (i - 3 >= 0) dp[i] += dp[i - 3];
    if (i - 4 >= 0) dp[i] += dp[i - 4];
  }
  return dp[target];
}

State first, in plain words, before any code gets trusted: dp[i] is the count of distinct sequences that add up to exactly i credits. The transition falls out of one question — what was the last elective taken to arrive at i? Either a 3-credit one, leaving i - 3 for everything before it, or a 4-credit one, leaving i - 4. So dp[i] = dp[i-3] + dp[i-4], guarded against negative indices.

Trace target = 10 by hand: dp[0]=1, dp[1]=0, dp[2]=0, dp[3]=1, dp[4]=1, dp[5]=0, dp[6]=1, dp[7]=2, dp[8]=1, dp[9]=1, dp[10]=dp[7]+dp[6]=2+1=3. Three sequences land exactly on 10: 3+3+4, 3+4+3, 4+3+3 — and the table produced "3" without ever listing them out.

dp[i] only ever reads two specific earlier entries — four and three steps back — never anything further. That means the full array can shrink to a small rolling window:

function waysToReachCreditsOptimized(target) {
  const window = [1, 0, 0, 0];   // window[k] holds dp[i] once i % 4 === k, rolling forward
  for (let i = 1; i <= target; i++) {
    const fromThree = i - 3 >= 0 ? window[(i - 3) % 4] : 0;
    const fromFour = i - 4 >= 0 ? window[(i - 4) % 4] : 0;
    window[i % 4] = fromThree + fromFour;
  }
  return window[target % 4];
}

Same rolling-variable idea the two-variable version of climbing stairs uses — the only difference is a transition that reaches back four steps instead of two, so the window needs to hold four values instead of two. Generalized: however far back a 1D transition ever looks, that's how big a window it needs, and no bigger.

Drill this shape on Dynamic Programming.