In finite one-pass dynamic programming, a dependency graph becomes a set of stored answers. Each state is solved after the states it depends on, written once, and then reused by later transitions.
The formulation starts with a state definition, base cases, and a recurrence over already-solved states. In the finite one-pass cases covered here, dependencies form an acyclic order. Recursion follows that order lazily. Iteration writes it out as loops. Optimization DP usually relies on optimal substructure, assembling an optimum from smaller optima. Counting and decision problems use the same machinery without optimizing. Repeated states make storage worthwhile, though repetition affects efficiency rather than correctness. Other DP methods, including value iteration, may revisit mutually dependent estimates until they converge.
Core shape for finite one-pass DP: state + base cases + recurrence + acyclic dependency order → each reached state solved once → (number of distinct states) × (transition work per state) time.
Visualization
Greedy
Largest usable coin first: exact change, but 6 coins instead of 3.
Naive Recursion
Try every first coin. Repeated remainders rebuild the same work.
Memoization
Keep recursion, but save each answered remainder beside the counter.
Tabulation
Build exact change from 0¢ upward on a visual amount board.
Memoization (Raw)
The raw view shows the canonical recursion tree, cache hits, and stored returns.
Both examples become DP only after the state discards irrelevant history. Coin change keeps the remaining amount because every denomination remains reusable; finite coin stock would also require the remaining counts. Grid path keeps the current coordinate. Two calls with the same state have the same future choices and therefore the same answer, regardless of how they arrived there.
Top-down (memoisation) follows the recurrence from the target. The first visit to an amount or coordinate computes it; later visits return the saved answer. It may skip unreachable states, but it pays call-stack cost. Memoization develops that reuse mechanism independently of DP.
Bottom-up (tabulation) starts from known answers and fills every state its target may depend on. Coin change advances from 0¢ to 30¢; grid path moves backward from the dispatch door. The loops make dependency order explicit and avoid recursion.
The recurrence then names the dependencies. Coin change reads best[amount - coin] for every usable denomination and keeps the minimum plus one. Grid path reads the right and down suffix costs and adds the current tile. The animations differ because those state spaces differ—a one-dimensional amount board versus a two-dimensional matrix—but the storage rule is the same.
A cashier must return exactly 30¢ using real 1¢, 10¢, 25¢, and 50¢ denominations. The example assumes enough of each coin that stock is not a constraint. Taking the largest usable coin first returns 25 + 1 + 1 + 1 + 1 + 1, while 10 + 10 + 10 uses half as many coins. The five tabs keep that counterexample fixed while changing the solving strategy and level of abstraction.
The simplified Memoization and Tabulation tabs keep the cashier model visible. Memoization (Raw) exposes the transferable recursion tree beneath the counter: each node is a remaining amount, and a cache hit closes a repeated subtree. The exact approaches compute 30¢ → 3 coins; they differ in which states are visited first and whether control lives in the call stack or a loop.
Coin-change state flow
flowchart LR
A["best(30¢)"] -->|"use 1¢"| B["best(29¢) + 1"]
A -->|"use 10¢"| C["best(20¢) + 1"]
A -->|"use 25¢"| D["best(5¢) + 1"]
C --> E["best(10¢) + 2"]
E --> F["best(0¢) + 3"]
B --> G["other valid continuations"]
D --> H["five 1¢ transitions"]
F --> I["minimum: 3 coins"]
G --> I
H --> I
Coin change, top-down and bottom-up (C#)
static int FewestCoinsTopDown(int amount, int[] coins){ ArgumentNullException.ThrowIfNull(coins); ArgumentOutOfRangeException.ThrowIfNegative(amount); if (amount == int.MaxValue) throw new ArgumentOutOfRangeException(nameof(amount), "amount + 1 must fit in Int32."); if (coins.Any(coin => coin <= 0)) throw new ArgumentException("Coin denominations must be positive.", nameof(coins)); var memo = new Dictionary<int, int> { [0] = 0 }; var answer = Solve(amount); return answer > amount ? -1 : answer; int Solve(int remaining) { if (memo.TryGetValue(remaining, out var cached)) return cached; var best = amount + 1; foreach (var coin in coins) { if (coin > remaining) continue; var suffix = Solve(remaining - coin); if (suffix <= amount) best = Math.Min(best, suffix + 1); } memo[remaining] = best; return best; }}
static int FewestCoinsBottomUp(int amount, int[] coins){ ArgumentNullException.ThrowIfNull(coins); ArgumentOutOfRangeException.ThrowIfNegative(amount); if (amount == int.MaxValue) throw new ArgumentOutOfRangeException(nameof(amount), "amount + 1 must fit in Int32."); if (coins.Any(coin => coin <= 0)) throw new ArgumentException("Coin denominations must be positive.", nameof(coins)); var dp = Enumerable.Repeat(amount + 1, amount + 1).ToArray(); dp[0] = 0; for (var remaining = 1; remaining <= amount; remaining++) foreach (var coin in coins) if (coin <= remaining) { var suffix = dp[remaining - coin]; if (suffix <= amount) dp[remaining] = Math.Min(dp[remaining], suffix + 1); } return dp[amount] > amount ? -1 : dp[amount];}
FewestCoinsTopDown(30, [1, 10, 25, 50]) and the bottom-up version both return 3. The contract requires 0 <= amount < int.MaxValue and strictly positive denominations; those constraints keep dependencies acyclic and the sentinel arithmetic valid.
A warehouse robot may move only right or down from the loading bay to the dispatch door. Choosing the cheaper immediate tile and breaking ties to the right walks into an expensive corridor and costs 21; the best complete route costs 10. Naive recursion eventually finds it, but different route prefixes repeatedly reach the same coordinate.
Greedy
Choose the cheaper next tile, breaking ties right. Later costs trap the route.
Naive Recursion
Explore every right/down route and revisit the same coordinates.
Memoization
Write solved remaining costs into the warehouse map and reuse repeated tiles.
Tabulation
Fill the warehouse map backward from the dispatch door and reveal the route.
Memoization (Raw)
The raw view shows the canonical coordinate recursion tree and cache hits.
Here the state is a coordinate rather than an amount. best(R2C2) means “the minimum remaining cost from this tile,” independent of how the robot arrived. The four simplified tabs use one warehouse matrix with integrated context, while Memoization (Raw) exposes the canonical recursion tree. Memoization stops repeated calls to a saved coordinate; tabulation makes the dependency order spatial by reading the already-solved tiles to the right and below.
Grid-path state flow
flowchart LR
A["best(R1C1)"] -->|right| B["best(R1C2)"]
A -->|down| C["best(R2C1)"]
B -->|down| D["best(R2C2)"]
C -->|right| D
D --> E["minimum of right and down"]
E --> F["dispatch door"]
R2C2 is one state even though two route prefixes reach it. Memoization computes its suffix once; tabulation fills it once before either predecessor reads it.
Grid path, top-down and bottom-up (C#)
static long CheapestPathTopDown(int[,] cost){ ArgumentNullException.ThrowIfNull(cost); var rows = cost.GetLength(0); var columns = cost.GetLength(1); if (rows == 0 || columns == 0) throw new ArgumentException("The cost grid must be nonempty.", nameof(cost)); var memo = new long?[rows, columns]; return Solve(0, 0); long Solve(int row, int column) { if (row == rows - 1 && column == columns - 1) return cost[row, column]; if (memo[row, column] is long cached) return cached; long suffix = row == rows - 1 ? Solve(row, column + 1) : column == columns - 1 ? Solve(row + 1, column) : Math.Min(Solve(row + 1, column), Solve(row, column + 1)); var answer = checked((long)cost[row, column] + suffix); memo[row, column] = answer; return answer; }}
static long CheapestPathBottomUp(int[,] cost){ ArgumentNullException.ThrowIfNull(cost); var rows = cost.GetLength(0); var columns = cost.GetLength(1); if (rows == 0 || columns == 0) throw new ArgumentException("The cost grid must be nonempty.", nameof(cost)); var dp = new long[rows, columns]; for (var row = rows - 1; row >= 0; row--) for (var column = columns - 1; column >= 0; column--) { if (row == rows - 1 && column == columns - 1) { dp[row, column] = cost[row, column]; continue; } long suffix = row == rows - 1 ? dp[row, column + 1] : column == columns - 1 ? dp[row + 1, column] : Math.Min(dp[row + 1, column], dp[row, column + 1]); dp[row, column] = checked((long)cost[row, column] + suffix); } return dp[0, 0];}
Both versions require a nonempty grid and return the same checked long route cost. Explicit edge transitions prevent an out-of-grid sentinel from winning against a large valid suffix. The visualization keeps the full table so it can also highlight the chosen route.
Complexity
Dynamic Programming complexity
m
number of coin denominations considered at each state
n
target amount in the coin-change comparison
Boundaries
A DP formulation is only as sound as its state definition and recurrence. Reuse and table shape decide whether it is practical.
The state omits necessary history. A coordinate is sufficient because movement is restricted to right and down and the remaining tile costs depend only on position. Fuel, keys, or visited-tile restrictions would also have to become part of the state.
The dependency order is cyclic. Right/down movement forms a DAG. Unrestricted movement can introduce cycles, so one recursive or tabulated pass no longer works. The problem needs a graph shortest-path algorithm or another convergence rule.
A state may be unreachable. Coin change without a 1¢ denomination can leave some amounts impossible. Its sentinel must pass through the recurrence without overflowing, and the public result must distinguish “no solution” from a large valid answer.
No states repeat. A memo with no cache hits adds overhead. This is the usual divide-and-conquer regime: merge sort has a valid recurrence, but every subarray state is unique.
Optimization DP still needs a valid composition rule. For the same US-coin drawer, the largest-coin rule returns 25 + 1 + 1 + 1 + 1 + 1 for 30¢. The recurrence compares every allowed predecessor and finds 10 + 10 + 10. The greedy algorithms note explains why that local rule fails and when it is safe.
Questions
What changes between memoization and tabulation if the recurrence is the same?
Memoization and tabulation evaluate the same recurrence and store one result per state. They differ in how the evaluation order is determined and which states get computed.
Memoization (top-down): starts from the requested state, recursively follows its dependencies and caches each result the first time it is computed.
Tabulation (bottom-up): loops fill the stored results in an order where every dependency is already available.
Aspect
Memoization (top-down)
Tabulation (bottom-up)
Evaluation order
Recursion from the target discovers dependencies as it goes, so no order has to be written down. The dependencies must still be acyclic.
The loops must visit states in an order that solves every dependency before any state that reads it.
States computed
Only states reachable from the target are computed, so unneeded states are skipped.
Every state in the planned table is computed, including states the target never reads.
Control cost
Each call costs a function call and a cache check. Recursion depth follows the longest dependency chain, so very deep chains can overflow the call stack.
Plain loops avoid recursive calls and their stack-depth limit.
When both compute the same set of states with equivalent work per state, their asymptotic time is identical: the number of states times the work per state.
Coin change with a 30¢ target shows the two orders. Memoization starts at best(30) and recurses into the smaller remaining amounts it needs. Tabulation fills best[0] through best[30] in increasing order, which works because each amount reads only smaller amounts.