LeetCode Dynamic Programming Pattern — From Memoization to Tabulation

Direct answer: Dynamic Programming (DP) solves a problem by defining a smaller state, solving each needed state once, and reusing those results. Use it when choices create overlapping subproblems and the answer for a larger problem can be built from answers to smaller ones. A complete DP solution has four parts: a precise state meaning, base cases, a recurrence or transition, and an order that computes dependencies before dependents. Without all four, a table is only a guess.

For example, in Climbing Stairs, let dp[i] mean the number of ways to reach step i. The final move came from i - 1 or i - 2, so dp[i] = dp[i - 1] + dp[i - 2]. Because smaller states repeat in a recursive solution, caching or filling them once changes exponential repeated work into O(n) work.

Pattern Recognition Signals and Anti-Signals for Dynamic Programming

Recognition signal	State often describes	Classic family
Count the number of ways	Position, remaining amount, or prefix length	Climbing Stairs, Decode Ways
Minimum or maximum result across choices	Best result up to an index or capacity	House Robber, Coin Change
Can we make or reach a target?	Index plus sum, amount, or boolean reachability	Subset Sum, Word Break
Compare two sequences	A pair of prefix indices	Longest Common Subsequence, Edit Distance
Optimal path through a grid or interval	Cell coordinates or interval endpoints	Minimum Path Sum, Burst Balloons

Anti-signals: DP is not automatically best because a problem asks for a maximum. If a locally optimal choice has a proof that it never harms the global answer, a greedy algorithm may be simpler. If the data are sorted and the task is about a pair, try Two Pointers. If the answer is a contiguous range that can be repaired by removing a left prefix, try Sliding Window. If there are no repeated states, plain recursion, graph traversal, or backtracking may be more direct.

State Is the Contract of a DP Solution

Before writing code, complete this sentence: “dp[... ] is the answer to _____ using exactly the information encoded by _____.” For a one-dimensional array, dp[i] might mean the best answer using the first i values, ending at i, or starting at i. Those meanings are different and lead to different transitions. For a two-dimensional table, dp[i][j] often means an answer for prefixes of lengths i and j, not necessarily values at indices i and j.

The invariant for bottom-up DP is: before computing the current state, every state named on the right side of its recurrence already holds its correct answer. The loop direction is therefore part of correctness, not a performance detail. In top-down memoization, the equivalent invariant is: once solve(state) returns, the cache stores the correct answer for that state, and future calls reuse it.

Design step	Question to answer	Example for Climbing Stairs
State	What does one cell mean?	Ways to reach step i
Base cases	Which smallest states are known directly?	dp[0] = 1, dp[1] = 1
Transition	Which prior states lead here?	dp[i - 1] + dp[i - 2]
Order and answer	When are dependencies ready, and which state is returned?	Fill i from 2 through n; return dp[n]

Memoization and Tabulation Templates

1. Top-down memoization

function climbStairsMemo(n) {
  const memo = new Map();

  function dp(step) {
    if (step <= 1) return 1;
    if (memo.has(step)) return memo.get(step);

    const ways = dp(step - 1) + dp(step - 2);
    memo.set(step, ways);
    return ways;
  }

  return dp(n);
}

Memoization follows the recurrence naturally and visits only states reached by the query. Use memo.has, not a truthiness check, because valid cached values can be 0 or false in other problems. Its costs here are O(n) time, O(n) cache space, and O(n) recursion-stack space.

2. Bottom-up tabulation with space optimization

function climbStairs(n) {
  if (n <= 1) return 1;

  let twoBack = 1;
  let oneBack = 1;

  for (let step = 2; step <= n; step += 1) {
    const current = oneBack + twoBack;
    twoBack = oneBack;
    oneBack = current;
  }

  return oneBack;
}

Only the two previous states are needed, so the full table is unnecessary. The update order matters: compute current before overwriting either previous value. This version remains O(n) time but uses O(1) auxiliary space.

3. 0/1 subset-sum template and loop direction

function canPartition(nums) {
  const total = nums.reduce((sum, num) => sum + num, 0);
  if (total % 2 !== 0) return false;

  const target = total / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;

  for (const num of nums) {
    for (let sum = target; sum >= num; sum -= 1) {
      dp[sum] = dp[sum] || dp[sum - num];
    }
  }

  return dp[target];
}

Here dp[sum] means “this sum is possible using numbers processed so far.” Iterating sums downward prevents the current number from being reused within the same outer iteration. For an unbounded problem such as Coin Change, iterate upward instead when reuse in the same iteration is intended. This direction distinction is a frequent interview test.

Common DP Families and Variants

Family	State shape	Important decision
1D sequence DP	One index or a rolling few values	Take/skip, previous values, or ending condition
Grid DP	Row and column	Which predecessor cells can enter this cell?
Two-sequence DP	Two prefix lengths	Match versus skip one character or element
0/1 knapsack	Item prefix and capacity, often compressed	Each item may be used once; iterate capacity downward
Unbounded knapsack	Amount or capacity	Reuse is allowed; the recurrence and order permit it
Interval DP	Left and right endpoints	Fill shorter intervals before longer intervals

Top-down is often clearer for sparse state spaces, complex transitions, or memo keys with several dimensions. Bottom-up avoids recursion-depth limits and makes dependencies explicit. Neither is automatically superior; choose the form that makes the state and initialization easiest to defend.

Worked Dry Run: Climbing Stairs

Let n = 5 and define dp[i] as ways to reach step i. There is one way to stand before climbing, so dp[0] = 1; there is one way to reach step 1, so dp[1] = 1. Then dp[2] = 1 + 1 = 2: either 1 + 1 or 2. Next, dp[3] = 2 + 1 = 3, dp[4] = 3 + 2 = 5, and dp[5] = 5 + 3 = 8.

The rolling-variable version keeps exactly the values needed for the next transition. Before step 4, twoBack = dp[2] and oneBack = dp[3]. Compute 5, then shift the names forward. This dry run checks both the recurrence and the update order; if the base case or shift is wrong, the first few rows reveal it.

Complexity, Boundaries, and Edge Cases

State-space shape	Typical time	Typical storage
One index with constant transitions	O(n)	O(n), often reducible to O(1)
n by m table	O(nm)	O(nm), sometimes reducible to O(m)
Items by target capacity	O(n × target)	O(target) after compression
All intervals	Often O(n3)	Often O(n2)

Define empty-prefix states deliberately: they often make the recurrence cleaner. Use Infinity for an impossible minimum and a suitably low sentinel for an impossible maximum, but never add to a sentinel without considering the result. Watch integer limits; JavaScript Number loses integer precision above Number.MAX_SAFE_INTEGER, so a counting prompt may require a modulus or BigInt. For recursive solutions, account for stack depth. For two-dimensional DP, allocate the extra row and column when your state represents prefix lengths, which removes many boundary branches.

Common Failure Modes

• Writing a recurrence before defining what the state means, then returning the wrong cell.
• Choosing base values that do not agree with the state definition.
• Using a forward capacity loop for 0/1 knapsack and accidentally reusing one item many times.
• Using a backward loop for an unbounded problem and accidentally preventing allowed reuse.
• Checking a memoized value by truthiness even though 0 or false is a valid answer.
• Optimizing a table to one row before proving which previous row and column values are needed.
• Ignoring unreachable states, overflow, recursion depth, or the empty input.

Deliberate Practice Ladder

1. Start with Climbing Stairs and House Robber. Say the state, base cases, and recurrence before typing.
2. Solve Min Cost Climbing Stairs and Coin Change to distinguish minimum objectives from counting objectives and to handle impossible states.
3. Practice Partition Equal Subset Sum, then explain why 0/1 capacity iteration goes downward.
4. Solve Unique Paths and Longest Common Subsequence to build confidence with two-dimensional prefix states.
5. Finish with Edit Distance, Longest Increasing Subsequence, or an interval problem only after deriving a transition on paper.

Repeat a solved problem in both top-down and bottom-up forms. If the two versions disagree on a small hand-built test, inspect the state definition before changing the code.

Mock-Interview Explanation Checklist

• Give the brute-force choice tree briefly and identify the repeated state that causes duplicate work.
• State in one sentence what each DP cell or memo key means.
• List base cases and explain why they follow from that definition.
• Derive the transition from the final choice, move, or match decision.
• Specify iteration order and why every dependency is ready; call out downward versus upward capacity loops when relevant.
• State time and space in terms of the state space, then test empty, impossible, and smallest nontrivial inputs.

Connect This Pattern to the Rest of Your Prep

DP retains results for repeated states; Two Pointers eliminates candidates using ordering, and Sliding Window maintains one contiguous range with exact incremental state. Review all three through the LeetCode category, then practice communicating the same fundamentals with the software engineer interview questions guide.

GhOst can support personal preparation and mock interviews by helping you rehearse a state definition, dry run, and edge-case checklist. Use assistance during an actual interview or assessment only if it is explicitly permitted by the applicable rules. Consult the relevant platform guidance and compatibility information before using any tool.