A dynamic programming method that advances a boundary across a structured object and records only the information needed on that boundary. For tilings by pieces of bounded height, a bit mask recording occupied cells in a few frontier rows can determine every legal continuation. Its state space is typically exponential in the width but independent of the total height.
Pseudo-polynomial time Created 2026-10-14 Updated 2026-11-05
An algorithm has pseudo-polynomial time when its running time is bounded by a polynomial in the numerical magnitudes of input quantities, rather than necessarily in their encoded lengths. The dynamic programming table for the 0-1 knapsack problem uses arithmetic operations for items and capacity .
A binary numeral system representation needs only bits for that capacity, so the table bound can be exponential in the number of capacity bits. For example, capacities below fit in bits, while a table with one entry for every capacity can have nearly columns. The numerical-value bound does not claim that every instance requires exponential work.
Richard Bellman Created 2026-10-13 Updated 2026-11-05
Richard Bellman developed dynamic programming, organizing multistage decisions through the optimal value of a smaller remaining problem. The Bellman equation expresses that recursive relationship between a present choice and its future consequences.
The approach connects optimization, control theory and stochastic decision models. It can replace enumeration of complete decision histories by a reusable state description, although a large state space can still make computation expensive. His 1957 book collected central results of this program.[ref]
For integer weights, subset-sum dynamic programming finds the greatest achievable total at most in time , where is the total weight. For rational weights and , scale by and round down to . The scaled total is at most , so exact dynamic programming costs arithmetic operations. Lifting its partition to the original weights increases the maximum load by at most . Thus it is a fully polynomial-time approximation scheme for this two-bin problem. Bit complexity also accounts for the rational input and epsilon encodings.
Smith-Waterman algorithm Created 2026-10-20 Updated 2026-11-05
The Smith-Waterman algorithm finds an optimal local sequence alignment for a specified additive scoring scheme. For a linear gap penalty , a dynamic programming score satisfies
Zero permits an alignment to restart; tracing back from the largest entry to zero recovers a highest-scoring segment pair. Every optimal ending must have one of the listed final steps, which proves the recurrence by induction over the table. Optimality concerns this score, not guaranteed biological ancestry. [ref]
State compression Created 2026-10-20 Updated 2026-11-05
State compression replaces a dynamic programming history by a smaller summary that retains everything needed to determine future legal choices, costs and transitions. Histories may be merged only when their summaries make all relevant continuations equivalent.
For selecting a subset of objects, an -bit mask stores membership in one integer. A path problem may additionally need the final vertex: two partial paths visiting the same subset can have different continuation costs if their endpoints differ. Compression saves storage by discarding irrelevant history; omitting relevant state changes the problem rather than optimizing its solution.
Stochastic control Created 2026-10-07 Updated 2026-10-14
A stochastic control problem chooses an admissible control input using information available in a filtration to optimize an expected objective for a random dynamical system. Dynamic programming often characterizes its value function through a Hamilton-Jacobi-Bellman equation.
Stochastic game Created 2026-10-20 Updated 2026-11-05
A stochastic game combines a state space with strategic choices and probabilistic state transitions. At each stage, the current state and players' actions determine immediate payoffs and a probability distribution for the next state. A discounted, average-reward or finite-horizon rule specifies how stage rewards are aggregated.
With a single decision maker this reduces to a Markov decision process. With several players, a policy that is best against one fixed opponent may cease to be best when that opponent changes policy. A two-player zero-sum game discounted model leads to a statewise minimax Bellman equation, connecting strategic reasoning with dynamic programming.
A strictly increasing subsequence selects indices of a sequence with . Equal values cannot both occur in it. Its maximum possible length is , with ; in general for the weak longest increasing subsequence. Use strict comparisons in the dynamic programming recurrence relation and replace the first tail at least as large as the next value in the binary search algorithm.
Subset DP Created 2026-10-20 Updated 2026-11-05
Subset DP is dynamic programming indexed by subsets of a finite ground set, usually encoded by bit masks. A recurrence builds a subset from smaller subsets or removes one chosen element. There are subsets of an -element set, so many such methods require exponential space or time despite avoiding factorial enumeration.
For a shortest path visiting a given set, stores the best cost of a path visiting exactly and ending at . The recurrence retains the endpoint because it controls the next edge cost. Initial states and prohibited edges must be specified separately.
For the single-source problem, let be the minimum cost of a directed walk from to using at most edges. Set and for , use for finite , and let a minimum over an empty set be . Then
Every entry on the right comes from the previous round, requiring separate old and new arrays. The proof is the last-edge decomposition: a permitted directed walk either already uses at most edges, or ends with some after a prefix using at most . Conversely, each candidate describes a permitted directed walk. This dynamic programming viewpoint gives an exact meaning to every intermediate label, even when negative-cost directed cycles exist. Apply the formula to the source too: its initial zero is not a permanent constraint.
If no negative-cost directed cycle is reachable from , removing repeated-vertex portions of a directed walk cannot increase its cost. Whenever a destination is reachable, some shortest directed path therefore uses at most edges, and . Unreachable vertices keep distance . For in-place passes, every finite label still comes from a discovered directed walk; moreover, pass has offered every prefix of length of a shortest directed path, regardless of scan order. Its labels can improve faster than the synchronous labels, while the same upper bound on passes remains valid. This is why repeated local corrections eventually settle a global shortest path problem.
Temple F. Smith 2026-11-05
Temple F. Smith coauthored the algorithm for finding maximally similar segments within longer molecular sequences, now known as the Smith-Waterman algorithm. Its dynamic programming table permits a fresh start at score zero; a high-scoring segment can therefore begin and end inside either input rather than being forced to span both entire sequences.[ref]
The zero option is a mechanistic part of the optimization: it discards a sufficiently unfavorable preceding alignment. Alignment traceback begins at a largest table entry and ends at zero. This supports finding a conserved region embedded within otherwise different sequences; the resulting similarity still requires biological interpretation rather than automatically proving a particular evolutionary history.
Totient chain Created 2026-10-20 Updated 2026-11-05
The sequence obtained by iterating Euler's totient function on a positive integer. Since for , the sequence reaches 1. Counting both endpoints gives the length recurrence relation and ; increasing order of therefore suffices for dynamic programming.
Treewidth 2026-10-25
The minimum width of a tree decomposition. A tree has width at most one, while a clique of vertices forces width at least . Every pair of vertices in the clique shares a bag; their connected bag connected subgraphs of a tree have a common intersection by the Helly property of connected connected subgraphs of a tree, placing the whole clique in one bag. Small treewidth is useful for dynamic programming on finite-domain constraint satisfaction problems.
Typesetting demerit 2026-11-05
A typesetting demerit is a contribution to the paragraph cost minimized by the Knuth-Plass line-breaking algorithm. It combines spacing quality with break preferences and, when applicable, costs involving neighbouring lines. Thus typesetting badness is one input to the cost rather than the entire objective.[ref]
Consider the ordinary finite-penalty case in TeX, away from its integer saturation and recovery cases. Let be the TeX line penalty, the typesetting badness and the typesetting penalty, with and . The base contribution is
Charges for incompatible line-breaking fitness classes or consecutive hyphenated lines can then be added.
For an illustrative choice , and , the base is . Changing only to gives . If an adjacency charge of 100 applies, those become 1025 and 975. These are chosen example parameters, not asserted defaults.
Dynamic programming compares accumulated costs while retaining the dynamic programming state needed by future charges. The lowest-cost break considered alone need not produce the lowest-cost complete text paragraph.
Unbounded knapsack problem Created 2026-10-20 Updated 2026-11-05
In the unbounded knapsack problem, each item type may be used any nonnegative integer number of times. With positive integer weights , values and capacity , maximize subject to and .
A dynamic programming recurrence for capacity-at-most value is . Evaluate capacities in increasing order so repeated uses are available. With weights three and five, values four and seven, and capacity ten, two weight-five items give value fourteen. A zero-weight positive-value item would make the objective unbounded, explaining the positive-weight hypothesis.
Weighted interval scheduling assigns each job a reward and maximizes their sum over compatible jobs. Earliest finish can fail for this different objective function; dynamic programming can compare alternatives.[ref]
For a separate two-job example, let have reward one and reward ten. Earliest finish accepts and rejects , earning one; the optimum accepts , earning ten. Replacing by preserves job count but loses reward. Thus the interval scheduling exchange argument proves the unit-value theorem only: its preserved quantity must match the intended objective function.