225: Dynamic Programming I: State, Recurrence, Memoization, and Tabulation

Learning outcomes

By the end of this lesson, you can:

explain and apply state definition in a realistic implementation;
explain and apply recurrence in a realistic implementation;
explain and apply memoization in a realistic implementation;
explain and apply tabulation in a realistic implementation;
explain and apply base cases in a realistic implementation.

These outcomes are connected. You should be able to move from a problem statement to a precise state, derive the recurrence from that state, choose top-down or bottom-up evaluation, and initialize the smallest cases without changing what the state means. You should also be able to justify the resulting time and space costs and diagnose the bugs that appear when one of those decisions is inconsistent.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from a previous project where the same kind of concern appeared: perhaps a repeated calculation, a bounded resource decision, a retry path, or a data-processing step that depended on earlier results. The point is not to memorize DP vocabulary. It is to connect the vocabulary to a defensible decision in both an interview-sized problem and a production data-processing problem.

When you recall that example, ask what information a later decision actually needed, which inputs could overlap, and what would happen if the input were empty, malformed, or much larger than expected. Those questions lead naturally to state design and to the operational constraints that matter around the algorithm.

Terminology

State definition: Write a sentence such as dp[i] = best answer for prefix ending before i. The sentence is the contract for each stored value; without it, an array of numbers is only an implementation detail with no reliable interpretation.
Recurrence: Express the current answer from strictly smaller states and justify every transition. The recurrence describes why a state can be computed from the information already represented by those smaller states.
Memoization: Top-down recursion plus a cache computes only reachable states and mirrors the recurrence. It also incurs call-stack overhead and requires stable keys when the state has multiple dimensions, so it is not automatically the best production choice.
Tabulation: Bottom-up DP orders states so their dependencies have already been computed. It avoids recursion depth and often makes memory compression easier, although it may compute states that a particular input never reaches.
Base cases: Base values represent the smallest subproblems and must agree with the state semantics. A convenient-looking initialization is wrong if it describes a different problem.
Complexity from states/transitions: Time is roughly the number of states multiplied by the transitions considered for each state; space is the stored states plus any recursion stack. Counting these directly is usually more dependable than guessing from the shape of nested loops.

Mental model

Treat Dynamic Programming I: State, Recurrence, Memoization, and Tabulation as a design problem with observable inputs, outputs, invariants, and failure modes. Dynamic programming is useful when subproblems overlap and an optimal or counting result can be expressed in terms of smaller states. The difficult step is not writing the loop or the cache. It is choosing a state that contains exactly the information future decisions need: omit relevant information and the recurrence becomes incorrect; include too much and the state space may become needlessly large.

A strong implementation makes its assumptions visible, narrows uncertainty at the boundaries, and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to explain why the design is safe. The same discipline applies outside interview problems. A data-processing job may still need a clear state, an invariant, bounded memory, and a response to malformed or incomplete input.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Start by translating the requirement into an answer that can be checked. Then identify the input limits and whether the task asks for a minimum, maximum, count, feasibility result, or reconstruction of a choice. From there, state what must remain true after each transition. Do not jump from the requirement directly to a library call or a familiar DP template. First make the invariant explicit; then choose the mechanism that enforces it.

Deep dive

1. State definition

The first question is not “should I use an array?” It is “what does one entry mean?” Write a sentence such as dp[i] = best answer for prefix ending before i. If that sentence is vague, the recurrence and base cases will be unstable because you will not know whether an index represents an item, a boundary between items, or a prefix that includes the item at that index.

The state should retain every fact that can change a future decision, and no fact that the future does not need. For a one-dimensional problem, that may be an index. For a constrained problem, it may be an index plus remaining capacity, current balance, or another dimension. The invariant is the sentence you wrote: every stored value must continue to satisfy it after each update.

Decision rule: Use state definition deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. In a review, ask someone to interpret dp[i] without reading the implementation. If two reasonable readers give different answers, the state is not ready for a recurrence.

2. Recurrence

Once the state is precise, express the current answer from strictly smaller states and justify every transition. A recurrence is a proof structure, not only a code pattern. Each option in the problem should correspond to a transition, and the combination operation should match the requested result: min, max, addition, or a boolean choice are not interchangeable.

Check that every dependency is genuinely smaller or otherwise already available under the chosen evaluation order. Then ask whether the recurrence covers all legal choices without counting one choice twice. This is where people usually get confused: a recurrence can look plausible and still solve a subtly different problem if its index convention or transition set is off by one.

Decision rule: Use recurrence deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. State the transition in words before writing code; that gives you something concrete to test against the normal case and the smallest cases.

3. Memoization

Top-down memoization starts with the recurrence as a recursive function. Before calculating a state, the function checks a cache; after calculating it, the function stores the result. This computes only reachable states and often mirrors the problem statement closely, which can make the first correct implementation easier to inspect.

That convenience has costs. Recursion consumes call-stack space, deep inputs can exceed the stack limit, and a multidimensional state needs a stable cache key. The cache must also distinguish an absent entry from a legitimate result such as 0, false, or an empty value. If it does not, the algorithm may recompute states or incorrectly treat an uncomputed state as a computed answer.

Decision rule: Use memoization deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. It is a good fit when the state graph is sparse or when the recursive choices naturally avoid many states; it is less attractive when all states are reachable or recursion depth is a production risk.

4. Tabulation

Bottom-up tabulation fills a table in an order that guarantees every dependency is ready before the current state is evaluated. The table makes the progression visible and removes recursion-depth risk. It can also reveal that a state depends only on a small sliding window of earlier values, which permits memory compression after correctness is established.

The trade-off is that a table may calculate every state, including states that a top-down implementation would never visit. The iteration order is part of the algorithm, not a cosmetic choice: if a cell is read before its dependency has been initialized, the result can be wrong even when the recurrence itself is correct.

Decision rule: Use tabulation deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Prefer it when predictable work, shallow control flow, or bounded stack usage matters; document the order and the meaning of each row or column so later memory optimization does not erase the reasoning.

5. Base cases

Base values represent the smallest subproblems and must align with state semantics. For example, if a state describes an empty prefix, its value may be the neutral answer for the operation; if it describes a nonempty prefix, the initialization must not silently include an empty case. Many off-by-one bugs are actually a mismatch between the state meaning and initialization.

Derive base cases from the recurrence's stopping points rather than copying values from a familiar problem. Test the smallest input by hand and trace the first transition. Also decide how invalid input is handled at the boundary; “no solution,” “invalid input,” and a valid result of zero are different outcomes when the contract distinguishes them.

Decision rule: Use base cases deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. A base case is correct only when both the value and the index interpretation agree with the state definition.

6. Complexity from states/transitions

Time is roughly the number of states times the transitions considered per state; space is the stored states plus the recursion stack. This is more reliable than inspecting nested loops after implementation. A one-dimensional table with n states and constant work per state is typically O(n) time; adding a second bounded dimension changes the count to the product of those dimensions.

Count reachable states separately from possible states when comparing memoization and tabulation. Memoization may do less work on sparse input, while tabulation usually offers a more predictable bound. If only the previous two states are needed, compressed storage may reduce auxiliary space, but only after confirming that no later reconstruction step needs the discarded values.

Decision rule: Use complexity from states/transitions deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. State the cost before optimizing, and include stack space for top-down implementations rather than reporting only the cache size.

Worked example

Consider an interview-sized problem and a production data-processing problem. In both settings, begin with the requirement instead of reaching for a memorized template. Write the requirement in one sentence, list the input and output contracts, and identify which concept owns each failure mode. For a DP problem, that means naming the state, explaining the recurrence, identifying the base cases, and deciding whether all states need to be computed.

The important move is separation: parsing or validation belongs at the boundary; domain rules belong in the domain/service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing these concerns can make a happy-path demo look shorter, but it makes edge cases and failures much harder to reason about. An algorithm should receive data that satisfies its stated contract, or it should return an explicit invalid-input result rather than quietly inventing one.

The following implementation solves the minimum-cost path through a sequence of costs using only the previous two DP results. prev1 and prev2 represent the two states needed by the recurrence; the update order preserves those dependencies before advancing:

function minCost(cost: readonly number[]): number {
  let prev2 = 0;
  let prev1 = 0;
  for (const value of cost) {
    const current = value + Math.min(prev1, prev2);
    prev2 = prev1;
    prev1 = current;
  }
  return Math.min(prev1, prev2);
}

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For this particular pure function, retries and concurrency do not mutate shared state, so repeated calls with the same valid input are safe; in a production pipeline, that property must not be assumed for surrounding persistence or side effects. For each case, state which layer detects the problem and what the caller observes.

Also inspect the algorithm's contract before generalizing it. The function accepts a readonly numeric array, but it does not itself validate missing input, non-finite numbers, or overflow concerns. Those are boundary and domain decisions, not reasons to obscure the recurrence. This is the level of explanation expected in a senior code review or technical interview: describe the state and invariant, identify what the code does not guarantee, and connect each failure mode to its owning layer.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. A DP routine may be deterministic, yet the job that calls it can still duplicate writes, exceed memory, receive partial input, or expose a stale result. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted. The algorithm's correctness is one layer of the system's correctness, not a substitute for these boundaries.

Guided lab

Solve climbing stairs and minimum coin change both top-down and bottom-up. Write the state, recurrence, and base case first, then compute complexity from state count and transition count. For each version, explain whether it computes only reachable states, what its maximum recursion depth is, and whether its stored state can be compressed without losing information.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

For the lab, include a hand-worked trace for a small input. Compare the memoized and tabulated state counts, then test a case where no solution exists for minimum coin change. The goal is not just to produce two accepted functions; it is to show that both implementations preserve the same state semantics and answer the same contract.

Edge cases and failure modes

State definition: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Confirm that every index and dimension still has the meaning stated in the contract.
Recurrence: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify that every legal transition is included exactly once and that no dependency points outside the valid state range.
Memoization: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Check cache-key stability, cache misses, legitimate zero-like results, and recursion depth.
Tabulation: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Check initialization and iteration order, especially at the first state and at the final boundary.
Base cases: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Hand-check the empty and smallest valid inputs against the state definition.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
Testing only the happy path and therefore discovering contracts only after integration.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.

For debugging, reproduce the smallest failing case, inspect the actual value or execution plan, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. In a DP implementation, print or inspect a short table or the sequence of computed states. If the first incorrect value appears at initialization, inspect the base case; if it appears after a transition, compare the recurrence's words with the code; if values are unexpectedly recomputed, inspect the memoization key and cache sentinel; if the result is correct but memory is excessive, count stored states before compressing them.

Interview questions

What problem does State definition solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Recurrence solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Memoization solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Tabulation solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Base cases solve, and what trade-off or failure mode would make you choose a different approach?

Answer these with a concrete example rather than a definition alone. A strong answer names the state invariant, gives one transition, identifies the base case, and explains why the selected evaluation strategy fits the constraints. It should also mention what would make the alternative preferable.

Checkpoint

Without notes, explain Dynamic Programming I: State, Recurrence, Memoization, and Tabulation to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code.

Before considering the checkpoint complete, trace at least one input by hand and state the time and space complexity from the number of states and transitions. If you cannot explain what one stored value means, return to the state definition before changing the implementation.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.