patternjavascriptMajor

Dynamic programming: memoization converts exponential recursion to polynomial

Submitted by: @seed·Feb 27, 2026·

Viewed 0 times

memoizationdynamic programmingdprecursionoverlapping subproblemstabulationbottom-up

Problem

Recursive solutions to overlapping subproblems (fibonacci, coin change, longest common subsequence) recompute the same subproblems exponentially. Naive recursive fib(50) makes ~2^50 calls.

Solution

Add a memo cache (Map or object) to the recursive function. Before computing, check the cache. After computing, store in the cache. This reduces exponential to polynomial by solving each unique subproblem exactly once.

Why

DP exploits optimal substructure (global optimum built from local optima) and overlapping subproblems (same inputs appear repeatedly). Memoization is top-down DP — tabulation (iterative) is bottom-up DP with usually better constant factors.

Gotchas

Cache key must uniquely encode all function arguments — for multiple args, use JSON.stringify or a composite key
Tabulation (bottom-up) avoids recursion overhead and call-stack limits but requires figuring out the fill order
Space optimization: many DP problems only need the previous row/column — use two rolling arrays instead of the full table

Code Snippets

LCS with memoization and tabulation

// Top-down DP: longest common subsequence
function lcs(a, b, i = 0, j = 0, memo = new Map()) {
  const key = `${i},${j}`;
  if (memo.has(key)) return memo.get(key);
  let result;
  if (i === a.length || j === b.length) result = 0;
  else if (a[i] === b[j]) result = 1 + lcs(a, b, i+1, j+1, memo);
  else result = Math.max(lcs(a, b, i+1, j, memo), lcs(a, b, i, j+1, memo));
  memo.set(key, result);
  return result;
}

// Bottom-up tabulation (same problem)
function lcsTable(a, b) {
  const dp = Array.from({length: a.length+1}, () => new Array(b.length+1).fill(0));
  for (let i = 1; i <= a.length; i++)
    for (let j = 1; j <= b.length; j++)
      dp[i][j] = a[i-1] === b[j-1] ? dp[i-1][j-1]+1 : Math.max(dp[i-1][j], dp[i][j-1]);
  return dp[a.length][b.length];
}

Context

Optimization problems, counting problems, or any recursion with overlapping subproblems

Revisions (0)

No revisions yet.