Dynamic Programming

MNEMONIC Each cell = the cells it leans on.

RECIPE The four-step DP recipe

Every DP solution follows the same checklist — work through these steps before writing a single line of code:

1. Define the state. Write a one-sentence English definition: “dp[i] = …”. The state must encode everything you need to answer the question for that sub-problem without re-examining the original input.
2. Write the recurrence. Express dp[i] as a function of strictly smaller states — dp[i-1], dp[i-1][j-1], etc.
3. Identify base cases. What is dp[0] (or dp[0][0])? These are the sub-problems so small the answer is obvious without recursion.
4. Choose top-down or bottom-up. Top-down (memoization): write the recurrence as recursion + a cache. Bottom-up (tabulation): fill a table in dependency order. Both have the same asymptotic cost; choose whichever makes the order clearest.

PRECONDITIONS Overlapping sub-problems + optimal substructure

DP applies only when the problem has both of these properties:

• Overlapping sub-problems. The same smaller question recurs many times in a naive recursion tree. Without overlap, divide-and-conquer is enough (and memoization adds no benefit).
• Optimal substructure. The optimal answer to the full problem can be built from optimal answers to sub-problems. If the best solution to the whole depends on a non-optimal sub-solution (e.g. because sub-choices interact), DP cannot be applied directly.

TAXONOMY The six DP sub-families

Recognizing which family a problem belongs to immediately suggests the right state shape:

• 1-D linear (Fibonacci / House Robber). dp[i] depends on a constant number of previous entries. Often space-optimized to two rolling variables.
• Kadane (running best). Track the best value ending at i; used for maximum subarray / subproduct. The recurrence is dp[i] = max(dp[i-1] + a[i], a[i]).
• 0/1 knapsack. Each item is used at most once. dp[w] over capacity; iterate capacity descending. Subset-sum and partition problems are 0/1 knapsack variants.
• Unbounded knapsack. Items may be reused freely (Coin Change, Coin Change II). Iterate capacity ascending.
• 2-D string / grid DP. dp[i][j] over two sequences or a 2-D grid (LCS, edit distance, unique paths, interleaving string).
• Interval DP. dp[i][j] represents the optimal answer over a contiguous sub-range [i, j]. Fill by increasing length (Burst Balloons).
• State-machine DP. Multiple explicit states per position (hold / sold / rest in Stock problems). The recurrence transitions between states at each step.

COST Why memoization transforms the complexity

The total work equals number of distinct states × work per state. For a 1-D problem with n positions that is O(n); for a 2-D string problem it is O(m × n). Space follows the same count unless you apply a rolling-row optimization to reduce a 2-D table to a single row.

RUN IT Each cell = the cells it leans on

TRIGGERS When you see ___ → reach for ___

Reach for DP when the problem asks for an optimum or count over choices and a greedy argument does not cleanly apply. The clearest signal is a naive recursion that revisits the same arguments repeatedly.

RED FLAGSWhen it's NOT this pattern

• A greedy proof exists. If you can show that always taking the locally optimal choice never forecloses a globally better one (exchange argument), greedy is simpler and faster. Activity selection, interval scheduling, and Jump Game I are greedy — not DP.
• All choices are independent.If sub-problems do not share any computation (e.g. the sub-problems partition the input without overlap), divide-and-conquer suffices. DP's cache only pays off when the same arguments recur.
• You need the actual items / path, not just the optimum value. DP computes the optimum naturally, but reconstructing which choices produced it requires either storing parent pointers or back-tracking through the table — easy to forget under interview pressure.
• Constraints are tiny (n ≤ 20). Exponential backtracking or bitmask DP may be the intended approach. Very small inputs are a cue that full enumeration is acceptable, and a clean recursive solution may score better than a complex DP table.

TEMPLATE Top-down memoization

When → The recurrence is easiest to express recursively, or the DAG of sub-problems is sparse (many states are never reached). Write the recursion first, then add a Map or array cache keyed on the arguments.

// dp[state] = answer for this sub-problem; compute once, reuse forever.
function solve(input: number[]): number {
  const memo = new Map<string, number>();

  // Define dp(i) = <your English state definition here>
  function dp(i: number): number {
    if (i < 0) return 0;           // base case — smallest valid sub-problem
    if (i === 0) return 1;         // base case
    const key = String(i);
    if (memo.has(key)) return memo.get(key)!;

    // Recurrence: combine dp of strictly smaller sub-problems
    const result = dp(i - 1) + dp(i - 2);   // example: Fibonacci shape
    memo.set(key, result);
    return result;
  }

  return dp(input.length - 1);
}

TEMPLATE Bottom-up 1-D tabulation (rolling variables)

When → The state is a single index and each cell depends only on the previous one or two. The rolling-variable form (no array at all) reduces space from O(n) to O(1).

// dp[i] = best answer considering only the first i elements.
// Space-optimised: keep only the previous two values (rolling variables).
function rob(nums: number[]): number {
  // prev2 = dp[i-2], prev1 = dp[i-1]
  let prev2 = 0, prev1 = 0;

  for (const n of nums) {
    // dp[i] = max(skip this house, rob this house + dp[i-2])
    const cur = Math.max(prev1, n + prev2);
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;   // dp[n]
}

TEMPLATE Bottom-up 2-D table (two sequences)

When → The problem involves two strings or sequences (LCS, edit distance, interleaving, distinct subsequences). Use 1-indexed rows and columns so that index 0 represents the empty prefix — base cases fill themselves with zeros.

// dp[i][j] = answer for s[0..i-1] and t[0..j-1] (1-indexed rows/cols → easy base cases).
function lcs(s: string, t: string): number {
  const m = s.length, n = t.length;
  // dp[0][*] = 0, dp[*][0] = 0 (empty prefix → LCS length 0)
  const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s[i - 1] === t[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;   // characters match → extend
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);  // skip one char
      }
    }
  }
  return dp[m][n];
}

TEMPLATE 0/1 vs unbounded knapsack

When → The problem asks for an optimal value or count over items with a capacity/budget constraint. The only difference between 0/1 and unbounded is the direction you iterate the capacity loop.

// dp[w] = best value achievable with capacity w.

// ---- 0/1 knapsack: each item used AT MOST ONCE ----
// Iterate capacity DESCENDING so each item is considered at most once.
function knapsack01(weights: number[], values: number[], W: number): number {
  const dp = new Array(W + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let w = W; w >= weights[i]; w--) {   // <-- descending!
      // dp[w] = max(skip item i, take item i)
      dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
    }
  }
  return dp[W];
}

// ---- Unbounded knapsack: each item used ANY number of times ----
// Iterate capacity ASCENDING so the same item can be reused.
function knapsackUnbounded(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (const coin of coins) {
    for (let w = coin; w <= amount; w++) {    // <-- ascending!
      // dp[w] = min coins to make amount w
      dp[w] = Math.min(dp[w], 1 + dp[w - coin]);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

PITFALL Under-specified state (missing a dimension)

The most common DP bug: your recurrence seems right but produces wrong answers because the state doesn't capture everything relevant. Classic example — stock problems with a transaction limit or cooldown. The fix is adding another dimension (e.g. dp[i][k][holding]) so the state is unambiguous. Always write the English definition first and ask: “Given only this state, can I answer the sub-problem without re-reading the input?”

PITFALL Wrong base cases or dp[0] boundary errors

Off-by-one in base cases ripples through the entire table. A reliable convention: use 1-indexed DP arrays (length n+1) so that index 0 represents the empty prefix or zero capacity — it naturally initializes to 0 or Infinity depending on the problem, and you never need a special guard for i-1 < 0.

For coin-change style minimums, initialize dp[0] = 0 (zero coins to make amount 0) and all other entries to Infinity so the Math.min update is correct from the start.

PITFALL Wrong iteration order (filling a cell before its dependencies)

Bottom-up DP is only correct when every cell is computed after all the cells it depends on. For 2-D problems this usually means outer loop over rows, inner over columns. For interval DP, loop by increasing length of the interval, not by left endpoint — otherwise dp[i][j]reads an entry for a longer interval that hasn't been filled yet.

PITFALL 0/1 vs unbounded knapsack: wrong inner-loop direction

Iterating capacity ascending in a 0/1 knapsack allows an item to be picked multiple times (because dp[w - weight] was already updated in this pass). Iterating descendingin an unbounded knapsack prevents reuse. This is the single most common knapsack implementation error; fix it with the mnemonic: “descend to restrict, ascend to repeat.”

PITFALL Off-by-one between string index and dp index

When using 1-indexed DP arrays for strings (dp length n+1), dp[i] corresponds to s[i-1]. Forgetting the -1 offset when reading the character (e.g. s[i] === t[j] instead of s[i-1] === t[j-1]) is silent and produces subtly wrong results that only manifest on certain inputs.

PROBLEMS