AI Glossary / Natural language and speech / Intermediate
Dynamic programming
Definition
Dynamic programming is a method for solving a problem by combining solutions to smaller subproblems and reusing their results. It is especially useful when the same subproblems recur. In NLP, it underlies methods for edit distance, sequence decoding, and parsing. The word “programming” here describes a problem-solving approach, not a particular programming language.
What it means
A naive search may repeatedly solve the same partial problem along different paths. Dynamic programming identifies a state that summarizes the information needed for future decisions, stores the result for that state, and reuses it.
The crucial work is defining the subproblems and the rule that combines them. For optimization tasks, the formulation must justify why optimal solutions to the relevant smaller problems can support an optimal larger solution.
This is not simply a synonym for caching arbitrary computations. A useful dynamic program has a structured recurrence and a valid dependency order or equivalent method for evaluating the states.
How it works
Define what each state represents, its base cases, and how it depends on smaller states. Then compute the values in an order that makes the dependencies available.
A bottom-up implementation fills a table. A top-down implementation can use recursion with memoization, computing and storing only the states it reaches. These approaches can implement the same underlying recurrence.
If the task needs the actual sequence of decisions rather than just its score, store suitable backpointers or reconstruct the choices afterward. Efficiency depends on the number of states and transitions, so dynamic programming does not automatically make every problem small or inexpensive.
Three practical examples
- A spelling tool computes the minimum number of edits needed to transform one string into another.
- A sequence model uses the Viterbi algorithm to find a highest-scoring state sequence under its model assumptions.
- A constituency parser combines analyses of shorter spans to build analyses of longer spans under a grammar.
Think of it this way
Think of assembling a large project from reusable completed subassemblies instead of rebuilding each one whenever it is needed. The analogy captures reuse. The important limit is that a subassembly's stored result must contain everything the larger task needs; an incomplete state description can make the combination invalid.
Worked example
Consider an invented minimum-edit-distance task from “cat” to “cut.” Allow insertion, deletion, and substitution, each costing one; matching identical characters costs zero. Let D(i,j) be the minimum cost for the first i source characters and first j target characters.
The base row and column are D(0,j)=j and D(i,0)=i. Each other cell takes the minimum of deleting a source character, inserting a target character, or matching/substituting the final pair.
With columns representing empty, c, u, t, the empty-source row is [0,1,2,3]. The row for source prefix c is [1,0,1,2]; for ca it is [2,1,1,2]; for cat it is [3,2,2,1].
The final value is one: substitute a with u. Each cell reuses previously computed prefix results instead of enumerating every complete edit sequence independently. The table also makes the stated cost model visible; changing substitution cost could change both the value and the set of optimal edit paths.
Illustrative case study
Fictional case: MatchDesk develops a tool for suggesting corrections to short product codes. A prototype recursively explores every possible edit sequence and repeats many identical prefix comparisons. The team reformulates the task using a table of prefix-pair edit costs.
Reviewers check the recurrence, empty-string cases, and the cost policy before comparing runtime. They also note that the lowest edit distance does not necessarily identify the user's intended code, so the ranking may need additional evidence.
This fictional case illustrates how dynamic programming addresses repeated computation while leaving the application-level interpretation separate. It does not claim a particular speedup or that edit distance alone solves product-code correction.
Common misconceptions and mistakes
Dynamic programming is not the same as a greedy algorithm. A greedy method makes local choices; a dynamic program compares combinations through its recurrence.
Do not assume that storing results repairs an invalid state definition. If future costs depend on information omitted from the state, reusing a single stored value can be wrong.
Avoid claiming universal efficiency. A formulation can still have too many states, costly transitions, or substantial memory requirements. The algorithm is exact only for the problem and assumptions it actually represents.
Business use
For business teams, the concept helps explain how some language-processing algorithms can search large combinatorial spaces without enumerating every complete possibility. It is relevant when reviewing latency, memory use, or reproducibility of a structured inference component.
A useful technical review asks what a state contains, which recurrence is used, and whether the output is a score or a reconstructed solution. Application review should then ask whether that mathematical objective matches the user's real need. Efficiently optimizing the wrong objective remains a product failure.
People also ask
Is dynamic programming always recursive?
No. It can be implemented by filling a table iteratively, or through recursion with stored results.
Does it always produce an approximate answer?
No. Many dynamic programs compute exact solutions to their specified recurrence and objective, although the model itself may simplify reality.
Does reusing subproblems guarantee a fast algorithm?
No. The number of states and transitions still determines time and memory costs.
Check your understanding
A program stores the best result for a prefix but omits a constraint that affects which continuations are allowed. Is reuse automatically valid because the result was cached?
Answer: No. The state must retain the information needed to evaluate future choices correctly. Caching an insufficient summary can discard a path needed for the true solution.
Related terms
- Memoization
- Edit distance
- Viterbi algorithm
- State space
- recurrence relation
- optimal substructure
- CKY parsing
- backpointer
Learn next
Fill a small edit-distance table by hand and trace one optimal path backward. Then compare the table with a naive recursive formulation, identifying exactly which subproblems would otherwise be recomputed.
More in Natural language and speech
- Document structuring - Document structuring is the natural-language-generation task of organizing selected information into a coherent document.
- Document-term matrix - A document-term matrix is a numerical table representing documents through selected text features.
- Dot product - The dot product of two real-valued vectors is the sum of the products of their corresponding components.
- Dynamic time warping - Dynamic time warping, or DTW, aligns two sequences while allowing differences in their local timing.
- Edge-factored - Edge-factored describes a structured model whose score for a graph or tree decomposes into contributions from its individual edges.
- EDU - EDU stands for elementary discourse unit: a minimal segment used as a building block in a discourse analysis, especially Rhetorical Structure Theory.
Sources
Sources: Jurafsky and Martin, Speech and Language Processing, Words and Tokens, minimum edit distance and dynamic programming: https://web.stanford.edu/~jurafsky/slp3/2.pdf The edit-distance recurrence, base cases and backtrace passages were independently read. A separate implementation reproduced every cell of the original cat-to-cut table under unit edit costs.
Previous: Dynamic perfect hashing Next: Dynamic range