· By John Kavanagh

How I Choose Dynamic‑Programming State

Labelled wooden drawers in a library card catalogue.
Image by Daniel, licensed from Unsplash.

An array named dp does not tell me much. It might contain minimum costs, numbers of routes, whether prefixes are reachable, or the best answer ending at a particular position. Those meanings lead to different initial values and different update rules, even when the loops look almost identical.

When I work through a dynamic‑programming problem, I try to write a sentence that describes one stored value before choosing the storage. If that sentence is vague, shortening the implementation usually makes the confusion harder to see. A very efficient wrong answer remains an awkward interview companion.

The examples below use four problems I have worked through in my articles and comparison lab. The interesting part is not recognising a famous pattern. It is deciding which information a smaller problem must retain so that its answer remains useful later.


Start with the Question One Entry Answers

I want a state definition specific enough that I can calculate a tiny instance by hand. "The best answer so far" is usually missing something: best according to which measure, and over which part of the input?

Here are four more useful sentences:

  • Word Break: reachable[i] says whether the first i characters can be split entirely into dictionary words.
  • Unique Paths: ways[row][column] counts routes from the start to that particular cell.
  • Longest Common Subsequence: lengths[i][j] is the best common subsequence length within the two prefixes of lengths i and j.
  • Coin Change: fewest[amount] is the minimum number of available coins needed to make exactly that amount.

Each sentence fixes both the input represented by the index and the meaning of the value. It also tells me what the final lookup should be. A prefix table normally returns the entry for the complete prefix; an "ending here" table might instead need a maximum over every endpoint.

That distinction matters in my Longest Increasing Subsequence article: the longest increasing subsequence does not have to end at the final array position. Reading the last entry of the quadratic endpoint table would answer a narrower question.


Keep Enough Information to Distinguish Future Choices

Two partial histories can share a state when their future possibilities are equivalent for the question being answered. We can then retain only the summary that matters, rather than every route used to reach it.

In my Word Break implementation, once a prefix ends at position i, the remaining characters and the fixed dictionary determine every possible continuation. The number of words used to reach i does not matter when the question is merely whether a split exists. A boolean is sufficient.

Keeping only the length of the most recently chosen word would lose the current position in the string. Keeping only a preferred greedy split loses alternatives. With "cars" and the dictionary "car", "ca", and "rs", the longest first word leaves an unmatched s; the shorter first word gives ca + rs. The state must preserve that second reachable endpoint.

For two‑string comparison, one prefix length is not enough. The same prefix of the first string can have different common‑subsequence lengths against different prefixes of the second. My Longest Common Subsequence article therefore keeps both coordinates. Even the sets of characters are insufficient: "ab" and "ba" share two distinct letters but have a common subsequence length of only one.

I use these small collisions as a design check. If two inputs receive the same proposed state but require different next decisions or answers, the state has forgotten something necessary.


Let the Answer Type Choose the Combination Rule

Once the state is clear, I look at the last decision that could have produced it. The possible predecessors are not enough on their own; we must combine their answers in the right way.

For Word Break, try a final dictionary word whose start follows a reachable prefix. Any successful predecessor is enough, so the operation is logical "or". For my Unique Paths explanation, a route reaches a cell from above or from the left. Those alternatives have different final moves, so their route counts can be added without counting the same route twice.

Coin Change minimises. For every coin no larger than the current amount, a reachable smaller amount gives a candidate of one additional coin. The update keeps the smallest candidate. Longest Common Subsequence maximises between skipped‑prefix alternatives when the current characters differ; when they match, it extends the earlier diagonal answer.

Changing the value type changes the problem. A boolean grid can tell us whether a route exists, but it cannot recover the three routes through a two‑by‑three empty grid. Adding Word Break booleans would not automatically produce a correct segmentation counter either: the counting state and its interpretation would need to be defined deliberately.

My first question about a transition is therefore "what do these values represent?" The operator follows from that answer, rather than from whatever appeared in the previous dynamic‑programming example.


Empty Does Not Always Mean Zero

Base cases express the smallest valid answers. They are not a ceremony for appeasing the loops.

Word Break uses reachable[0] = true: before consuming any characters, there is no unmatched text. This allows a dictionary word starting at the beginning to become a valid first step. It is an internal base case even though the official challenge requires a nonempty input string.

Unique Paths gives the starting cell one route: staying at the start before making a move. Setting every cell to zero and only adding predecessors would leave the whole grid at zero. Along a clear top edge or left edge, there remains exactly one route.

An empty prefix has a common subsequence length of zero. Coin Change also gives amount zero a value of zero, but other amounts start at infinity, meaning "not reached". Starting those entries at zero would invent free solutions. With denomination two, amount three stays unreachable and the public result becomes -1.

The symbols overlap, but their meanings do not. I write down why the base value is correct, including the impossible‑state marker, before deciding whether an array's default initialisation is helpful.


Follow Dependencies Before Saving Memory

Bottom‑up order should ensure that every predecessor has already been calculated. Positive coin denominations make smaller amounts suitable predecessors; prefix problems use shorter prefixes. A recursion with memoisation can visit the same dependency graph on demand, provided its cache key contains the complete state.

Compressing storage adds a second question: does a cell currently hold the previous stage's answer or this stage's answer? In a rolling Unique Paths row, the value above is still in the current slot, whilst the value to the left has already been updated. The loop needs both, so left‑to‑right traversal is intentional.

The rolling common‑subsequence version also needs the old diagonal. It saves that value before overwriting the current slot. Replacing it with the updated left value can claim two matches between "ab" and "aa", reusing a character that only exists once.

Loop order can change reuse rules too. In a coin‑by‑coin update, scanning amounts upwards lets a coin contribute again to a later amount in the same pass. Scanning downwards reads the previous pass's possibilities and permits each listed coin only once. With one denomination of two and target four, those interpretations give two coins and no solution respectively.

That does not mean "always loop forwards". It means the state's stage and reuse rule must survive the storage optimisation. I keep the expanded version until I can name the old and new values at each assignment.


Test the Meaning, Then Count the Work

I want tests that would distinguish plausible wrong definitions. My lab checks the greedy Word Break trap, the boolean‑versus‑counting grid, the lost diagonal, and the coin‑reuse example. It also checks the familiar greedy coin trap: denominations one, three, and four need two coins for amount six, whereas choosing four first uses three.

Those are targeted counterexamples, not a proof that every input works. For the full implementations, independent small‑input oracles provide a different check: enumerating subsequences, exploring segmentation cuts, or calculating exact route counts. Comparing two versions of the same faulty recurrence would be less revealing.

Once the definition and transitions hold together, I count states and work per state. The common‑subsequence table has a product of two prefix lengths and constant work per cell. Coin Change checks the available denominations at each amount. Word Break also performs string slicing and dictionary lookups, whose character‑processing cost should not disappear from an explanation just because a Set is involved.

My Dynamic Programming Comparison Lab keeps these cases beside the working solutions. The deliberately wrong examples are labelled and tested for their expected failure; they are there to expose lost information, not as alternatives to copy into an application.


The Sentence I Come Back to

Before changing a table into a rolling array, I read its state definition again. Does it still describe the value at the moment the transition reads it? That one question catches wrong endpoints, missing coordinates, accidental reuse, and overwritten dependencies. It is a more useful starting point than trying to decide how many nested loops a dynamic‑programming solution ought to have.

Downloadable Resource

  • Dynamic Programming Comparison Lab

    Run my fourteen TypeScript solutions across seven problems, with independent checks for string edits, decoding counts, staircase routes, prefixes, and subsequences.

    Download ZIP

Untangling a delivery problem?

Send the symptoms, constraints, and affected routes. I'll help identify whether the issue sits in the application, platform, content model, deployment path, or search surface.