226: Dynamic Programming II: Knapsack, Subsequences, Grids, and State Compression

Learning outcomes

By the end of this lesson, you can:

explain and apply 0/1 knapsack in a realistic implementation;
explain and apply unbounded knapsack in a realistic implementation;
explain and apply longest common subsequence in a realistic implementation;
explain and apply longest increasing subsequence in a realistic implementation;
explain and apply grid dp in a realistic implementation.

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 you had to choose between remembering all prior data and retaining only the small part needed for the next step. It might have involved a running total, a retry calculation, a table of previous results, or a two-dimensional dependency. The point is not to memorize DP vocabulary. The point is to make a defensible decision in both an interview-sized problem and a production data-processing problem, reasoning from constraints rather than from a familiar template.

Terminology

0/1 knapsack: Each item may be used at most once. The 0/1 describes the choice for an item: exclude it or include it one time. Treat this as a precise engineering constraint, not merely vocabulary.
Unbounded knapsack: Items may repeat. Capacity often iterates forward so states newly computed for the current item can contribute again. That loop direction is not a stylistic preference; it encodes the reuse rule.
Longest common subsequence: Two indices describe prefixes of two sequences. A subsequence keeps relative order but may skip elements; it does not require the selected elements to be adjacent.
Longest increasing subsequence: The classic O(n²) DP is straightforward to reason about. An O(n log n) patience/binary-search method computes the length more efficiently, but reconstruction requires additional bookkeeping and the meaning of its working array is easy to misunderstand.
Grid DP: A cell's path count or cost often depends on top, left, or diagonal neighbors. The movement rules determine which dependencies are valid and how the first row and column are initialized.
State compression: Compress dimensions only when the recurrence uses a bounded set of previous layers and the update order does not destroy values still needed in the current iteration. Lower memory usage is useful only if the resulting invariant remains provable.

Mental model

Treat Dynamic Programming II: Knapsack, Subsequences, Grids, and State Compression as a design problem with observable inputs, outputs, invariants, and failure modes. Dynamic programming is not one particular nested-loop shape. It is a way to define smaller states, express how a state depends on earlier states, and ensure that every dependency has already been computed when it is read.

The families in this lesson differ in what “earlier” means. Knapsack states move through items and capacities. Subsequence states move through prefixes or through earlier positions. Grid states move through neighboring cells. State compression changes how much history is retained, but it does not change the recurrence that must be satisfied. A strong implementation makes assumptions visible, narrows uncertainty at boundaries, and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to prove why the design is safe.

A useful interview and production sequence is:

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

Do not jump from a requirement directly to a library call or a loop copied from a solution bank. First state what must remain true. Then define what one table entry means, which earlier entries it can depend on, and whether the output is a value, a count, a decision, or a reconstructed path. Only then choose the storage layout and iteration order that enforce that meaning.

Deep dive

1. 0/1 knapsack

The problem is to choose from a fixed set of items while respecting a capacity, usually maximizing value. Each item is available once. If dp[i][c] means the best value using the first i items with capacity c, the transition considers two choices: leave item i out, or include it when its weight fits. The second choice is based on the previous item layer, so the same item cannot enter the solution again.

A 2D table makes that rule explicit and is often the best first implementation. A 1D optimization stores the best value for each capacity and iterates capacity backward. With capacity moving from large to small, dp[c - weight] still represents the state before the current item was applied. If capacity moved forward, the value just written for this item could be read again, silently turning the algorithm into an unbounded version.

The useful invariant is: after processing an item, dp[c] is the best result obtainable from the items processed so far at capacity c. For the 1D form, the backward loop is part of that invariant. A typical time complexity is O(nC), with O(nC) storage for the explicit table or O(C) storage for the compressed form, where n is the number of items and C is capacity. That pseudo-polynomial cost is practical only when capacity is bounded enough for the chosen representation.

Decision rule: Use 0/1 knapsack 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. Validate that weights and capacity are non-negative and that the numeric range cannot overflow the chosen number type. Decide separately whether duplicate-looking records represent distinct items or accidental duplicate input.

2. Unbounded knapsack

Unbounded knapsack uses the same broad capacity/value idea, but an item can be selected repeatedly. This is the model behind problems such as making a target amount from reusable denominations or maximizing revenue from repeatedly available sizes. The recurrence is similar to 0/1 knapsack, but the source state for “take this item” is allowed to come from the current item layer.

In a 1D maximum-value formulation, capacity commonly iterates forward. When dp[c] is updated using dp[c - weight], that smaller-capacity state may already include the current item. Reading it is exactly what permits another copy. Reversing the loop would enforce at-most-once usage instead. Loop order is therefore part of the recurrence semantics, not an implementation detail that can be changed during refactoring.

The invariant is: while processing an item, each updated state represents the best result available under the items permitted by the recurrence, including repeated use of the current item when the model allows it. The usual time complexity is O(nC) and the compressed storage is O(C). For unbounded problems, also check whether a zero-weight positive-value item exists. Without a separate rule, that input makes the optimum unbounded rather than a normal finite DP result. For counting combinations, distinguish combinations from permutations; the outer-loop order often determines which one is counted.

Decision rule: Use unbounded knapsack 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 whether items may repeat, whether order matters, and what should happen when the target cannot be reached before writing the transition.

3. Longest common subsequence

When two sequences contain related information but insertions and deletions make their positions differ, comparing only equal indices misses valid matches. A longest common subsequence (LCS) keeps the relative order of selected symbols while allowing gaps. It is useful for diff-like comparisons, version analysis, and similarity logic where adjacency is not required.

Let dp[i][j] describe the LCS length of the first i elements of one sequence and the first j elements of the other. If the next symbols match, the result extends the diagonal state: dp[i][j] = dp[i - 1][j - 1] + 1. Otherwise, the optimal result must drop one side, so compare dp[i - 1][j] and dp[i][j - 1]. The empty-prefix row and column are zero, which gives the recurrence a clean boundary.

The invariant is that every table entry describes the optimal answer for exactly the two prefixes named by its indices. The standard table takes O(ab) time and O(ab) space for sequence lengths a and b; the length alone can be computed with O(min(a, b)) space. That compression is not enough when the caller needs the actual subsequence unless choices are stored or the table can be rebuilt or rewalked. Reconstruction walks backward: a diagonal move records a match, while a move toward the larger neighboring value drops one side. Ties need a deterministic policy if stable output matters.

Decision rule: Use longest common subsequence 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. Clarify whether equality is based on exact symbols, normalized text, IDs, or a domain-specific comparator; the DP cannot correct a comparison rule that is wrong at the boundary.

4. Longest increasing subsequence

The longest increasing subsequence (LIS) asks for the longest sequence of values in increasing index order whose values also increase. The selected values need not be adjacent. This is where people usually get confused: “increasing” may mean strictly increasing or non-decreasing, and the binary-search choice must match that definition.

The classic O(n²) DP is direct. For each position i, initialize its subsequence length to one, then inspect earlier positions j. If values[j] < values[i] for a strictly increasing subsequence, update the best length ending at i from the best length ending at j. Keeping a predecessor index makes reconstruction straightforward. The time complexity is O(n²), with O(n) storage.

The patience/binary-search method reduces the length calculation to O(n log n). Its working array does not necessarily contain the final subsequence. At each step, replace the first tail that is greater than or equal to the current value for strict LIS; the index of that replacement is the length position the value can support. Smaller tails are better future candidates, which is why replacement is useful even when it does not preserve the final answer directly. Reconstructing the sequence requires predecessor and position arrays in addition to the tails structure.

Decision rule: Use longest increasing subsequence 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. Test duplicates, already sorted input, reverse-sorted input, negative values, empty input, and a single element. State whether the caller needs only the length or the actual sequence before choosing the implementation.

5. Grid DP

Grid problems become manageable when each cell's result is defined in terms of cells that have already been reached. For a right-and-down path count, a cell commonly receives paths from the top and left. For a minimum-cost path, it receives the minimum of those predecessor costs plus its own cost. Diagonal movement, obstacles, blocked start/end cells, and alternate movement rules change the recurrence and the initialization.

The invariant should identify both the cell and the allowed movement history: once processing reaches (row, column), the stored value is the correct answer for that cell under the stated rules. Initialize the start carefully, then handle the first row and column according to whether their only predecessor is reachable. An obstacle must not be treated as an ordinary zero-cost or zero-count cell; it is unreachable, and its representation must not accidentally create paths through it.

For an r by c grid, the usual table costs O(rc) time and O(rc) space. If a row depends only on the previous row and values already updated in the current row, one-row compression reduces storage to O(c). A diagonal dependency needs a saved previous-diagonal value, and a recurrence that depends on farther or multiple prior layers may require more storage. Movement order and compression must be justified together.

Decision rule: Use grid dp 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. Define the coordinate convention, obstacle representation, numeric behavior for unreachable cells, and behavior for an empty or malformed grid before implementing the recurrence.

6. State compression

A full DP table is valuable because its indices make the state meaning visible. Compression is an optimization that removes dimensions only when those dimensions are no longer needed. The safe question is not “Can this array be smaller?” It is “Which previous states does the recurrence read, and will this update overwrite one before its last read?”

Compress dimensions only when the recurrence uses a bounded set of previous layers and update order does not destroy values still needed in the current iteration. Backward capacity iteration preserves the previous item layer for 0/1 knapsack; forward iteration intentionally exposes current-item results for unbounded knapsack. In grid DP, a left-to-right row update can retain the current row's left value while a separate variable preserves the prior row's diagonal value. These are different invariants and should not be mixed casually.

Compression usually changes storage, not asymptotic time. For example, a two-layer recurrence can move from O(nC) memory to O(C) while remaining O(nC) time. The trade-off is reduced debuggability and, often, loss of reconstruction information. Keep the full table when explaining the algorithm, diagnosing a failing case, or recovering choices is more important than memory. Compress only after writing down the full recurrence and checking the update order against a small hand-worked example.

Decision rule: Use state compression 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 smaller allocation is not automatically a better implementation if it makes correctness, observability, or future changes harder to establish.

Worked example

Consider both an interview-sized problem and a production data-processing problem. In either setting, start by writing the requirement in one sentence, list the input and output contracts, and identify which concept above owns each failure mode. For a DP implementation, include the meaning of one state, its base cases, its transition, the iteration order, and the expected time and storage costs. That short specification catches many bugs before the first loop is written.

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 makes a happy-path demo look shorter but makes malformed input, unreachable states, retries, and edge cases much harder to reason about. The DP function should receive data in a form its contract permits and return a domain result or a clearly defined error, rather than silently deciding what malformed input means.

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);
}

This function illustrates state compression for the minimum-cost climb recurrence. At each value, prev1 and prev2 represent the two prior states needed to calculate the next one; the older state is discarded only after it has been used. The function is intentionally small, but its contract still needs a decision: does an empty array mean zero cost, is a negative cost valid, and can values be large enough to overflow the numeric representation? The code also assumes the input is already a valid finite sequence of numbers.

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 function, the duplicate/retry case may be irrelevant because it is pure; that is itself a useful conclusion. For a service that computes DP input from a database or queue, the case becomes relevant: repeated delivery should not change the result unless the domain says it should. For each case, state which layer detects the problem and what the caller observes. This is the level of explanation expected in a senior code review or technical interview.

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 algorithm can be mathematically correct and still be the wrong production choice if an attacker or an ordinary data spike can make n, capacity, or grid dimensions allocate unbounded memory. 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. DP does not make untrusted input safe; validate dimensions, values, and numeric bounds before allocating tables or entering loops.

Guided lab

Implement 0/1 and unbounded knapsack with 2D then 1D DP, explain the opposite loop directions, and solve one LCS/grid problem with reconstruction or path recovery. For each implementation, write down what one state means before compressing it. Compare the 2D and 1D versions on the same small inputs so a memory optimization is shown to preserve the result rather than assumed to do so.

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.

The comparison should include a case where loop direction matters, a case with no valid solution, and a case where the answer is not enough because the actual choices or path must be recovered. Those cases make the distinction between value computation and reconstruction visible.

Edge cases and failure modes

0/1 knapsack: test absence, malformed input, zero capacity, items too heavy to choose, duplicates, ordering/concurrency where applicable, numeric overflow boundaries, and behavior at the smallest and largest credible sizes.
Unbounded knapsack: test absence, malformed input, zero capacity, unreachable targets, zero-weight items, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.
Longest common subsequence: test absence, malformed input, empty prefixes, repeated symbols, ties during reconstruction, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.
Longest increasing subsequence: test absence, malformed input, duplicates under both strict and non-decreasing definitions, negative values, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.
Grid DP: test absence, malformed or ragged rows, empty grids, blocked start/end cells, obstacles, duplicate-looking input where relevant, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong. First check whether items can repeat, whether order matters, and what output must be reconstructed.
Changing a loop direction without changing the model: forward and backward capacity loops encode different reuse semantics.
Misreading a compressed state: a 1D array may represent the previous layer, the current layer, or a deliberate mixture of both. State that invariant in a comment or nearby documentation when the update is non-obvious.
Treating zero as “unreachable” in a minimum-cost or path-count problem: zero may be a valid answer. Use an explicit sentinel or reachability representation.
Assuming an LIS tails array is the final subsequence: it supports the length calculation, but reconstruction requires predecessor information.
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 state or execution trace, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. Print or inspect a full table before inspecting a compressed one. Compare each compressed state against the corresponding row, layer, or cell in a deliberately simple reference implementation. A wrong final value is usually less informative than the first state whose defined meaning was violated.

Interview questions

What problem does 0/1 knapsack solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Unbounded knapsack solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Longest common subsequence solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Longest increasing subsequence solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Grid DP solve, and what trade-off or failure mode would make you choose a different approach?

When answering, do more than name a recurrence. Define the state, identify the dependency direction, state the time and space complexity, and give one edge case that would invalidate a casual implementation. For the knapsack questions, explain why opposite loop directions produce different semantics. For subsequences and grids, explain what information must remain available if the caller needs reconstruction rather than only a length, count, or cost.

Checkpoint

Without notes, explain Dynamic Programming II: Knapsack, Subsequences, Grids, and State Compression 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. A complete explanation should also say what each state represents and why its update order is safe; otherwise it is easy to repeat a pattern without understanding which problem it solves.

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.