Dynamic programming works by turning a difficult problem into a finite collection of smaller states, defining how those states depend on one another, and ensuring that each useful state is solved once rather than recomputed through every possible path.
The name can sound more mysterious than the method. A dynamic program is usually built from four decisions: what a state means, what answer is stored for that state, how one state transitions to smaller or earlier states, and in what order those states are evaluated. Memoization solves states on demand; bottom-up tabulation solves them in a planned dependency order.
This guide explains dynamic programming in computer science from first principles: overlapping subproblems, optimal substructure, state design, recurrences, transitions, base cases, memoization, tabulation, dependency graphs, solution reconstruction, time and space complexity, state compression, shortest paths, sequence problems, knapsack, interval DP, grid DP and the failure modes that make DP feel harder than it is.
How Recursion Works in Computer Science · How Memoization Works in Recursion · How X Works Hub
The Direct Answer: What Dynamic Programming Actually Does
Dynamic programming replaces repeated exploration with organised reuse. Instead of treating every route through a problem as a fresh calculation, it identifies when different routes reach the same future state and lets those routes share one solved answer.
That is why dynamic programming is especially effective when a problem contains overlapping subproblems. Different decision histories may arrive at the same remaining problem. Once the remaining problem is solved, its answer can be reused.
The deeper insight is state compression: forget the past details that no longer affect the future, retain exactly what still matters, and solve that smaller state space.
The Word ‘Dynamic’ Is Historical, Not a Description of Animation
Dynamic programming was named by Richard Bellman in the twentieth century. ‘Programming’ originally referred to planning or optimisation rather than writing software code, and ‘dynamic’ was part of the naming strategy around multistage decision processes.
Today the term refers to an algorithmic technique used far beyond optimisation, including counting, feasibility, sequence comparison and path problems.
The modern mechanism is easier to understand by focusing on states and dependencies rather than on the historical name.
The First Question Is Not ‘What Table Do I Build?’
The first question is: what information completely describes a subproblem?
A table is only a storage format. If the state is wrong, a beautifully filled table computes the wrong recurrence efficiently. If the state is right, the implementation can often be memoized recursion, an array, a matrix, a dictionary or a compressed rolling structure.
Adrian therefore writes the state definition in a sentence before writing any recurrence.
A State Is a Sufficient Description of the Remaining Problem
Suppose two different histories lead to the same index i and remaining capacity c in a knapsack problem. If every future possibility depends only on i and c, then those histories can share one DP state.
The state should contain enough information to determine the future answer, but no irrelevant history.
This is the heart of dynamic programming: different pasts become equivalent when they have the same computational future.
Overlapping Subproblems Create the Opportunity
Naive recursion often creates a tree of call occurrences. Dynamic programming becomes useful when many nodes in that tree represent identical states.
Memoization merges those repeated nodes by caching answers. Bottom-up DP never creates duplicate nodes in the first place; it schedules each distinct state directly.
The speedup comes from changing the unit of work from paths to unique states.
Optimal Substructure Explains Many Optimisation DPs
An optimisation problem has optimal substructure when an optimal solution to the full problem can be composed from optimal solutions to appropriately defined subproblems.
For example, if the shortest path to a destination through a chosen predecessor must contain a shortest path to that predecessor, subproblem optima can support the global optimum.
This property is common but should be justified, not assumed. A poor state definition can destroy the apparent substructure by hiding information needed for future decisions.
Dynamic Programming Is Not Only for Optimisation
A DP can count the number of paths, decide whether a string can be segmented, compute edit distance, find probabilities, recognise a language, evaluate a game state or count combinatorial objects.
The stored value may be a minimum, maximum, count, boolean, probability, set, score or richer object.
Optimal substructure matters for optimisation DPs; overlapping subproblem reuse is broader.
The Four-Part DP Design
A practical dynamic program usually has four visible parts: state, recurrence or transition, base cases, and evaluation order.
The state says what one cell or memo entry means. The transition says how its answer depends on other states. The base cases anchor the dependency structure. The evaluation order ensures prerequisites are available before a state is finalised.
Everything else—arrays, loops, recursion, dictionaries—is implementation.
State Variables Are Coordinates in a Problem Space
A one-dimensional DP might use dp[i]. A two-dimensional DP might use dp[i][j]. A state can also be a tuple such as (position, remaining budget, mode).
Each coordinate should have a semantic meaning. ‘dp[i][j]’ is not an explanation; ‘best score using the first i items with capacity j’ is.
Clear semantics make transitions easier to derive and bugs easier to find.
State Granularity Is a Trade-Off
A state that stores too little information merges situations whose futures differ. The recurrence becomes incorrect.
A state that stores too much history may remain correct but explode the number of states and destroy the performance benefit.
Good state design finds the smallest sufficient information.
The Recurrence Is a Law of Local Dependence
Once the state is defined, ask: if I knew the answers to smaller or predecessor states, how would I compute this one?
For Fibonacci, dp[n] = dp[n−1] + dp[n−2]. For grid paths, a cell may depend on the cell above and the cell to the left. For edit distance, a state can depend on neighbouring index pairs representing insert, delete or substitute choices.
The recurrence is the mechanism that connects the state graph.
Transitions Represent Legal Decisions or Structural Moves
In optimisation DPs, a transition often corresponds to a choice: take or skip an item, match or edit a character, choose a predecessor, split an interval, extend a subsequence.
In counting DPs, transitions add the number of ways from predecessor states. In feasibility DPs, transitions combine booleans.
Jo learns to derive transitions from the actual legal moves of the problem rather than from memorised formulas.
Base Cases Are States With Direct Answers
Dynamic programming still needs a foundation. Some states are solved without consulting other states.
The empty prefix, zero capacity, source vertex, length-zero interval or completed position often supplies the base layer.
A recurrence without valid base cases is a dependency system with no grounded values.
Evaluation Order Is a Topological Question
A DP state should be evaluated after the states it depends on. In top-down memoization, recursion discovers this order automatically along demand paths.
In bottom-up tabulation, the programmer chooses an order that respects dependencies.
Thinking of states as nodes in a directed dependency graph makes the ordering problem much clearer.
Top-Down Memoization Is Demand-Driven DP
Start with the target state. If it is cached, return it. If it is a base state, solve it directly. Otherwise recursively request predecessor states, combine their answers, store the result and return.
This computes only states reachable from the target under the recurrence.
The previous eduKateSG memoization pillar owns the cache mechanism in detail.
Bottom-Up Tabulation Is Schedule-Driven DP
Start from base states and fill states in an order that guarantees every dependency is already available.
There is no recursive call stack in the usual bottom-up form. Control flow lives in loops or explicit iteration over a topological order.
This can reduce overhead and make space compression easier.
Memoization and Tabulation Are Two Execution Plans
They can solve the same recurrence over the same state graph.
Memoization asks states as needed. Tabulation chooses an order in advance. Memoization naturally skips unreachable states; tabulation can offer compact arrays, predictable traversal and freedom from recursion depth.
The right choice depends on sparsity, dependency structure, implementation language and clarity.
A Dependency DAG Is the Hidden DP Structure
If every transition moves toward a smaller, earlier or otherwise acyclic state, the distinct subproblems form a directed acyclic graph.
Dynamic programming evaluates that DAG while reusing nodes reached from multiple parents.
Memoized recursion performs a demand-driven depth-first evaluation; bottom-up DP performs a planned topological evaluation.
Fibonacci Is a Tiny DP, Not the Definition of DP
Fibonacci is useful because the repeated states are visible. But it has only one state variable and an extremely simple recurrence.
Real DP design becomes interesting when the challenge is discovering the state itself.
Use Fibonacci to see reuse, then move quickly to grids, strings, budgets, intervals and graphs.
Grid Paths Show State Equivalence
Suppose you count paths from the top-left to each cell while moving only right or down. The number of ways to reach cell (r,c) depends on the cells above and left.
Many complete paths share the same suffix after reaching a cell. The coordinate is sufficient state because the future rules depend only on location.
The DP collapses exponentially many path histories into a rectangular state grid.
Obstacle Grids Show That State Meaning Includes the Environment
If some cells are blocked, the transition changes locally: blocked states contribute zero paths.
The grid configuration is fixed input, not necessarily a state variable, because it does not change during the computation.
This distinction—fixed problem data versus changing subproblem state—helps prevent bloated state definitions.
Knapsack Shows Why One Index Is Not Enough
In 0/1 knapsack, knowing which item index remains is insufficient. The future also depends on remaining capacity.
Therefore a common state is (i, c): best value obtainable using items from a particular range with capacity c.
Different histories that leave the same i and c can reuse the same future optimum.
Edit Distance Shows Two-Dimensional Prefix State
Edit distance between two strings can use state (i,j), representing the distance between prefixes or suffixes ending at those positions.
The transition considers deletion, insertion and substitution or match.
The full exponential edit-sequence tree collapses into O(mn) distinct index pairs.
Longest Common Subsequence Shows Choice Without Immediate Cost
When characters match, the state often moves diagonally and extends the common subsequence. When they differ, the recurrence chooses between dropping a character from one side or the other.
The DP stores the best achievable length for each prefix pair.
Reconstruction can later recover an actual subsequence by following choices backward.
Shortest Paths Connect DP to Graph Algorithms
On a DAG, shortest paths are a direct dynamic program: process vertices in topological order and relax outgoing edges.
Each state is a vertex’s best known distance once all predecessors have been processed.
This reveals that dynamic programming is not a narrow table trick; it is structured evaluation over dependencies.
Bellman-Ford Can Be Viewed Through DP State Expansion
A classic formulation defines the best distance using at most k edges. The state adds an edge-count dimension so dependencies become acyclic across k.
This illustrates a powerful design technique: add state information that restores an ordered dependency structure.
Sometimes the right DP state is created by making hidden progression explicit.
Sequence DPs Often Use Prefixes
Prefixes are useful because they create a natural smaller-to-larger order. A state summarises the answer for the first i elements, first j elements or both.
Suffix formulations can work equally well if the transitions and evaluation order are consistent.
Index direction is a design choice, not a law.
Interval DP Uses Start and End Coordinates
When a problem asks for an answer on every contiguous interval, a natural state is (l,r).
Transitions may split the interval at k, shrink one boundary or combine smaller subintervals.
Bottom-up order often proceeds by increasing interval length so shorter intervals are available before longer ones.
Tree DP Uses Parent-Child Structure
A tree DP can define a state for each node, sometimes augmented with whether the node is selected, matched, coloured or constrained by its parent.
Postorder traversal naturally evaluates child states before the parent.
The DP order follows the tree rather than a rectangular table.
Bitmask DP Encodes Small Sets as State
When a problem has a small universe of items and the future depends on which subset has been used, a bitmask can encode that subset compactly.
A state might be (mask, last), such as in travelling-salesperson style formulations.
The technique trades an exponential number of subsets for far fewer than an exponential number of full permutations.
Digit DP Tracks Prefix Constraints
Digit DP solves counting problems over numbers by scanning digits while storing state such as position, whether the current prefix is tight to a bound, and other properties like digit sum or automaton state.
The key is that many numerical prefixes have the same future possibilities once compressed into the same state variables.
This is dynamic programming as information compression.
Profile DP Compresses a Frontier
In tiling and grid problems, the full past arrangement may be irrelevant except for the occupancy pattern along the current frontier.
A bitmask profile stores exactly that boundary information.
The state says, in effect, ‘everything behind the frontier has been solved; only this interface can affect the future.’
Dynamic Programming Is Often About Forgetting Safely
To create a state, ask what parts of the past can be discarded without changing any future legal moves or outcomes.
The discarded history may be enormous. The retained state may be only a few indices or flags.
This safe forgetting is the conceptual compression that makes DP powerful.
Markov-Like Thinking Helps State Design
A good DP state has a Markov-style property: once the current state is known, earlier history is irrelevant to the future recurrence.
This does not mean the problem is probabilistic or a Markov chain. It means the chosen state is sufficient.
If the future still depends on something not encoded, the state is incomplete.
Optimal Substructure Can Fail Under Hidden Coupling
If choosing an apparently optimal subsolution prevents a better global combination later, a naive recurrence may fail.
The fix may be to add state that records the relevant coupling information, or the problem may require a different method.
Dynamic programming does not magically make local optima globally compatible.
Greedy and DP Differ in Commitment
A greedy algorithm commits to one locally preferred choice and discards alternatives. A DP typically preserves the best answer for multiple states so future consequences remain represented.
Some problems permit a proof that one local choice is always safe; then greedy can be simpler. Others require keeping competing possibilities separated by state.
Knowing why alternatives can be discarded is the difference.
Brute Force, Memoization and DP Are a Continuum
Brute-force recursion explores paths. Memoization merges repeated states. Bottom-up DP schedules the distinct states directly.
The mathematical recurrence may be visible in all three.
Thinking of them as transformations of the same dependency structure is more useful than treating them as unrelated techniques.
Time Complexity Usually Becomes States Times Transition Work
A practical estimate is: number of distinct states multiplied by the work needed to process transitions from each state.
If there are O(n²) states and each tries O(n) splits, the DP may be O(n³). If each state has constant-degree transitions, O(n²) states may yield O(n²) time.
This formula is one of the most reliable DP complexity tools.
Space Complexity Starts With the State Table
If every state value is stored, memory is roughly the number of states times the size of each stored answer, plus auxiliary structures and any recursion stack.
Two-dimensional DPs can easily become memory-bound even when time is acceptable.
Space analysis should happen during design, not after implementation.
Space Compression Exploits Limited Dependency Windows
If row i depends only on row i−1, earlier rows can be discarded once they are no longer needed.
A two-dimensional O(nm) table may then require only O(m) memory.
The recurrence remains the same; the storage schedule becomes more efficient.
One-Array Compression Can Change Update Order
When a DP is compressed in place, loop direction can determine whether a transition reads values from the previous logical layer or values already updated in the current layer.
0/1 knapsack is a classic example where capacity is iterated backward to prevent using the same item multiple times in one layer.
Space optimisation can therefore alter correctness conditions.
Reconstruction Requires Remembering Decisions or Recomputing Them
A DP that stores only the optimal value may not directly tell you which choices produced it.
To recover a path, subsequence or item set, store predecessor pointers or decisions, or walk backward by comparing neighbouring state values.
Value computation and solution reconstruction are separate mechanisms.
Tie-Breaking Is Part of Reconstruction Semantics
Multiple optimal solutions may have the same value. A reconstruction rule can prefer lexicographically smaller, fewer items, earlier indices or any documented tie policy.
If no policy is specified, different correct implementations may return different optimal solutions.
DP correctness can have both value and representation dimensions.
Base Values Encode Identity and Impossibility
Some states are impossible. Optimisation DPs often represent them with +∞, −∞ or a sentinel rather than zero.
Choosing the wrong impossible-state value can allow invalid transitions to compete with legitimate ones.
Base initialisation is part of the recurrence, not a clerical step.
Infinity Sentinels Need Arithmetic Care
If a language uses a large finite number instead of mathematical infinity, adding costs can overflow or wrap.
If using floating infinity, comparisons may work well but integer semantics may differ.
Representation choices matter at the implementation layer.
Booleans, Counts and Optima Use Different Combine Operators
A feasibility DP may combine predecessor states with OR. A counting DP may sum counts. A shortest-path DP may take minimum over cost-plus-predecessor. A maximum-score DP may take maximum.
Recognising the algebraic combine structure can make a recurrence easier to derive.
Do not copy a min/max template onto a counting problem.
Transitions Can Be Pull or Push
A pull DP computes a state by reading predecessor states. A push DP takes a solved state and updates its successors.
Both can be correct if the evaluation order preserves dependencies and duplicates are handled appropriately.
The choice can affect code clarity, sparse-state efficiency and reconstruction.
Sparse DP Uses Maps Instead of Dense Tables
If the theoretical state space is huge but only a small subset is reachable, a dictionary of active states can save substantial memory and time.
Top-down memoization is naturally sparse. Bottom-up DP can also propagate only reachable states.
Dense rectangles are not mandatory.
State Dominance Can Prune DP
Sometimes multiple states share coordinates except one state is never better than another for any future continuation. The dominated state can be discarded.
This idea underlies Pareto-frontier DPs and resource-constrained optimisation.
Pruning is safe only with a proof that the discarded state cannot lead to a better future.
Dynamic Programming and Finite-State Machines
If a problem’s relevant history can be represented by a finite automaton state, DP can combine position with automaton state.
This appears in pattern counting, digit DP and string constraints.
The automaton compresses history; DP propagates counts or scores through it.
Dynamic Programming and Probability
States can store probabilities or expected values. Transitions then combine outcomes according to probability laws.
Care is needed with cycles, infinite horizons and numerical stability.
The technique is still state-based reuse, even when the stored values are not deterministic optima.
Dynamic Programming and Games
Finite games can define states by position and player-to-move, with values such as win/loss, score difference or minimax value.
If the game graph is acyclic or can be solved with appropriate fixed-point methods, dynamic programming can reuse repeated positions reached through different move orders.
Transposition tables in game search are a close relative of memoization.
Dynamic Programming and Parsing
Chart parsers and sequence algorithms use DP to record which grammatical structures can span which substrings.
The same substring may be derived through many parse histories, so state-based chart entries prevent repeated work.
This is dynamic programming over linguistic structure.
Dynamic Programming and Bioinformatics
Sequence alignment, edit distance and related problems use matrices whose cells summarise optimal or feasible relationships between prefixes.
The table turns exponentially many alignment paths into polynomially many prefix-pair states.
DP became foundational in computational biology because state reuse matches the structure of sequence comparison.
Dynamic Programming and Operations Research
Bellman’s principle of optimality arose from multistage decision problems, where current decisions affect future states.
Resource allocation, inventory, scheduling and control can all be formulated with state variables, decision transitions and value functions.
Algorithmic DP is therefore part of a much larger family of sequential decision methods.
Finite-Horizon Control Uses Time as State
When decisions occur across stages, time or stage index often becomes an explicit state coordinate.
Backward induction computes the value of future states and then chooses the best current action.
The direction of evaluation can run from the final stage backward even though real-world time moves forward.
Why ‘DP Formula’ Memorisation Fails
Two problems can look different yet share the same state dependency; two problems can look similar but require different state because one has hidden history.
Memorising table shapes encourages pattern matching on surface features.
Better practice is to define what one state knows, what it forgets and why that is sufficient.
A Common Failure: State Missing a Future-Relevant Variable
Two histories are merged even though their future legal moves differ.
The recurrence looks efficient but silently reuses an answer that belongs to another subproblem.
This is the most fundamental DP correctness failure.
A Common Failure: State Contains the Whole History
The DP remains correct but nearly every path becomes a distinct state, eliminating overlap and producing exponential memory.
Ask which historical details can no longer influence the future.
Compression is the point.
A Common Failure: Recurrence Uses an Illegal Choice
A transition may accidentally reuse an item, cross a blocked edge, violate order or ignore a constraint.
Derive transitions from the problem’s legal operations and write their preconditions explicitly.
Tables do not validate semantics.
A Common Failure: Evaluation Order Reads Unfinished States
In bottom-up code, a state is computed before one of its prerequisites.
The resulting value may use default zeros or stale memory and still look numerically plausible.
Draw dependency arrows before choosing loop order.
A Common Failure: In-Place Compression Changes the Recurrence
Updating a one-dimensional array in the wrong direction can allow a current-stage value to influence another current-stage state when the original recurrence required previous-stage values.
Space compression is an algorithm transformation, not a mechanical deletion of rows.
Re-prove dependencies after compression.
A Common Failure: Wrong Impossible-State Initialisation
Using zero for impossible states can cause them to win a maximum or minimum transition.
Use a representation whose ordering matches impossibility, and guard arithmetic if necessary.
Initial values are semantic.
A Common Failure: Counting Paths Twice
Push transitions can accidentally add the same logical transition multiple times, especially in graphs or combinatorial state spaces.
Define whether each predecessor-successor relation is unique and whether order creates distinct objects.
Counting DPs require careful combinatorial semantics.
A Common Failure: Reconstruction Does Not Match the Value DP
The optimal score is correct but the recovered path violates constraints because parent pointers were updated inconsistently or ties were mishandled.
Test reconstructed solutions independently against the original rules.
Value correctness does not guarantee witness correctness.
A Common Failure: Assuming Every Problem With Recursion Needs DP
If subproblems do not overlap, memoization may add memory without saving work. If a greedy proof exists, DP may be unnecessarily expensive.
Dynamic programming is a tool for structured reuse, not a prestige technique.
Choose it when the state graph justifies it.
A Common Failure: Confusing State Count With Input Size
An input of size n can induce O(n), O(n²), O(nW), O(2ⁿ), or larger state spaces depending on the state variables.
Pseudo-polynomial DPs such as capacity-based knapsack depend on numeric magnitude W, not merely the number of bits needed to encode W.
Complexity should be expressed in the real state dimensions.
Pseudo-Polynomial Time Is Still Potentially Huge
O(nW) may look polynomial in symbols, but if W is a large integer represented compactly, runtime can be exponential in the input bit length.
This matters when judging whether a DP is theoretically efficient.
State coordinates have computational meaning beyond notation.
DP Optimisations Often Exploit Transition Structure
Monotone queues, convex hull tricks, divide-and-conquer optimisation, Knuth optimisation and other advanced techniques reduce transition work under additional mathematical properties.
They do not replace state design; they accelerate a recurrence after structure is proven.
Optimise only after the baseline DP is correct.
The Best DP Explanations Separate Three Layers
Layer one is the problem semantics: what decisions and constraints exist. Layer two is the state graph: what information survives and how states depend. Layer three is execution: memoization, loops, arrays, compression.
Mixing the layers makes DP feel like a bag of code patterns.
Separating them turns it into a repeatable reasoning method.
World Return: Dynamic Programming Is Institutional Memory for Computation
A brute-force search repeatedly rediscovers consequences it has already learned. Dynamic programming gives the computation memory.
Once the result for a state is known, every path that reaches that state can inherit the answer. The system stops valuing how it arrived and starts valuing what remains.
That principle appears beyond algorithms: good institutions, workflows and knowledge systems also avoid re-solving unchanged states.
Different Roles See the Same DP Differently
A mathematician sees recurrence relations. A programmer sees arrays and dictionaries. An algorithms researcher sees a DAG of subproblems. An operations researcher sees value functions. A compiler engineer sees state-space optimisation. A systems engineer sees memory and scheduling.
The vocabulary changes, but the invariant is stable: compress histories into reusable states and evaluate dependencies once.
Strong explanations keep that invariant visible.
A Practical DP Design Workflow
First, describe a brute-force or recursive solution so the choices are visible. Second, identify repeated future situations. Third, define the minimum sufficient state. Fourth, define the value stored for one state. Fifth, derive legal transitions. Sixth, define base cases. Seventh, choose memoization or a dependency-respecting bottom-up order. Eighth, count states and transition work. Ninth, decide whether reconstruction is needed. Tenth, consider space compression only after correctness is clear.
This workflow moves from meaning to mechanism to optimisation.
Skipping directly to a table is the fastest route to confusion.
How to Debug a DP
Write the state meaning beside the table. Check base states. Pick one nontrivial state and manually enumerate the legal choices that should feed it. Compare those choices with the recurrence.
For bottom-up code, verify loop order against dependencies. For memoization, log state keys and cache hits. For reconstruction, validate the returned witness separately.
Debug the recurrence, not only the final cell.
How to Teach DP Without Making It Look Like Magic
Begin from an obviously exponential recursion. Circle repeated states. Memoize it. Then list the unique states and reorder them bottom-up.
Students should see that top-down and bottom-up are two schedules over the same state dependency structure.
Only then introduce the wider family of state patterns.
Frequently Asked Question: Is Dynamic Programming Just Memoization?
No. Memoization is one top-down execution strategy for reusing solved states. Dynamic programming is the broader state-and-recurrence method, including bottom-up tabulation, dependency ordering, state compression and solution reconstruction.
The previous recursion cluster owns memoization as a mechanism; this master owns the larger DP architecture.
Frequently Asked Question: Is Every Recurrence Dynamic Programming?
No. A recurrence may generate mostly unique subproblems with little reuse, or it may be solved analytically rather than computationally.
DP becomes especially useful when a finite state space contains overlapping dependencies that can be reused.
Frequently Asked Question: Does DP Require an Array?
No. Dictionaries, maps, sparse sets, graphs, trees and custom structures can store states.
Array tables are common when state coordinates are dense integer ranges.
Frequently Asked Question: Does DP Always Find an Optimum?
No. It can count, decide, measure probability, evaluate costs or compute any recurrence over reusable states.
Optimisation is a major use case, not the definition.
Frequently Asked Question: How Do I Know What the State Should Be?
Ask what information from the past can still change future legal moves or outcomes. Keep that information; discard the rest.
If two histories with the same proposed state can have different futures, the state is incomplete.
Frequently Asked Question: When Should I Use Bottom-Up Instead of Memoization?
Bottom-up can be attractive when the dependency order is simple, most states are needed, recursion depth is undesirable, arrays are compact, or space compression matters.
Memoization can be attractive when the reachable state space is sparse or the recursive specification is much easier to express.
The Series Map
This master has three dedicated pillars. Dynamic Programming States explains how subproblems are represented. Dynamic Programming Transitions explains recurrences, choices and dependency edges. Bottom-Up Dynamic Programming explains tabulation, evaluation order and space compression.
The previous recursion cluster’s Memoization article remains the canonical owner of top-down caching, and this master links to it rather than duplicating it.
Sources and Further Reading
For memoization, subproblems and the first principles of dynamic programming, see MIT OpenCourseWare: Dynamic Programming I.
For additional DP examples and design patterns, see MIT OpenCourseWare: Dynamic Programming II.
For the recursion and memoization bridge, see eduKateSG: How Memoization Works in Recursion.
Final Synthesis: Dynamic Programming Is the Art of Remembering Only What the Future Needs
Dynamic programming works because many different histories lead to the same remaining problem. Once those histories are compressed into one sufficient state, the answer for that state can be solved once and reused.
The recurrence defines the local logic. Base cases ground it. The dependency graph determines evaluation order. Memoization explores it on demand. Tabulation schedules it deliberately. Reconstruction turns values back into concrete choices.
The hardest part is rarely filling the table. It is deciding what one state must remember—and what it can safely forget.
Continue the How X Works Series
How X Works Hub · How Recursion Works · How Memoization Works in Recursion
Pillar Explainers for This Master Guide
- How Dynamic Programming States Work | State Variables, Subproblem Identity and Remembering Only What Matters
- How Dynamic Programming Transitions Work | Recurrences, Choices, Dependencies and Legal State Moves
- How Bottom-Up Dynamic Programming Works | Tabulation, Evaluation Order and Space Compression
