Memoization (Top-Down DP) Pattern

When to use Memoization (Top-Down DP)

• You can articulate a clean recursive definition (f(n) = g(f(n-1), f(n-2), ...)) but a naive recursion recomputes the same subproblem millions of times.
• The state space is small and discrete (a single integer, a pair, or a (i, target) tuple) so a Map or array keyed on those arguments fits in memory.
• Bottom-up tabulation would force you to think backwards from the base cases — top-down lets you write the recurrence in its most natural direction.
• The problem has overlapping subproblems but you only need to evaluate the ones reachable from the entry call, not the full DP table.
• You want to short-circuit early when a subproblem fails (cache returns false / -Infinity) instead of filling every cell of a tabulated array.

Template

function solve(n) {
  const memo = new Map();
  function dp(state) {
    if (isBase(state)) return baseValue(state);
    if (memo.has(state)) return memo.get(state);
    let best = initialValue();
    for (const next of transitions(state)) {
      best = combine(best, dp(next));
    }
    memo.set(state, best);
    return best;
  }
  return dp(n);
}

Common mistakes

• Caching on an incomplete state — e.g. memoizing on (i) alone when the answer also depends on (i, remainingTarget). The cache then returns stale answers for different targets at the same index.
• On Combination Sum IV, returning 0 from the base case when target overshoots zero and forgetting to return 1 at exactly target == 0 — the base case must distinguish 'no valid combination' from 'one valid combination'.
• Using a Map keyed on stringified tuples without realizing the conversion cost dominates the recursion, making the top-down solution slower than the equivalent bottom-up table.
• Hitting the JavaScript recursion limit (~10,000 frames on most engines) on problems like Climbing Stairs with n = 50,000 — switch to iterative bottom-up or trampoline when n is large.
• On Word Break, recursing into every suffix without memoizing on the starting index — exponential blow-up on long strings with many small dictionary words.