Dynamic Programming, Table by Table

After reading this you will be able to fill an edit-distance table and a knapsack table by hand, read the winning choice in each cell, and trace the optimal answer backwards through either grid.

What dynamic programming actually is

Dynamic programming solves a big problem by solving small versions of it first, writing every answer in a table, and reading those stored answers instead of recomputing them. That is the whole trick. The word "programming" here means "tabulation," not writing code.

Take a concrete hook. You want to turn the word kitten into sitting using single-character edits: insert, delete, or substitute. How few edits are enough? Brute force would try every sequence of edits, and the count of possible sequences grows explosively. Dynamic programming instead builds a grid of 7 x 8 = 56 cells, fills each one with a small comparison, and reads the answer 3 out of the bottom-right corner. Three edits: substitute k with s, substitute e with i, add a g.

The two problems in this visualizer, edit distance and 0/1 knapsack, share the same skeleton. Break the problem into indexed subproblems, define one recurrence that links a cell to a few smaller cells, fill the table in an order that respects those links, then walk backwards to recover the choices.

When to reach for it, and when not to

Dynamic programming fits a problem when two conditions hold. First, optimal substructure: the best answer to the whole is built from best answers to parts. Second, overlapping subproblems: the same small question gets asked many times, so caching it pays off.

Edit distance has both. The distance between two prefixes depends on the distances between slightly shorter prefixes, and those shorter prefixes recur constantly. Knapsack has both too: the best value using the first i items at capacity w reuses the answer for the first i-1 items.

Skip dynamic programming when subproblems do not repeat. Merge sort splits into fresh, non-overlapping halves, so plain recursion is already efficient. Skip it also when a greedy rule provably wins: to make change with standard coins, always taking the largest coin works, and no table is needed. And beware memory. The knapsack table has size n \times W, so an item count of 50 with capacity 10{,}000 means 500{,}000 cells, which is fine, but capacities in the billions are not.

The savings are structural. Brute-force edit distance explores roughly 3^n edit sequences; the table needs only (m+1)(n+1) cells. For kitten to sitting that is 56 cells versus more than 10^{3} naive paths, and the gap widens fast.

The edit-distance recurrence

Let D(i, j) be the minimum number of edits to turn the first i letters of string A into the first j letters of string B. The recurrence is:

D(i,j) = \min\{ D(i-1,j) + 1,\; D(i,j-1) + 1,\; D(i-1,j-1) + c \}

Here D(i-1,j) + 1 is a delete from A, D(i,j-1) + 1 is an insert into A, and D(i-1,j-1) + c is a match or substitute. The cost c is 0 when the letters A_i and B_j are equal, and 1 when they differ. The three inputs are exactly the diagonal, left, and top neighbours of the current cell.

The base cases anchor the grid. To make an empty string from a prefix of length i takes i deletions, so D(i,0) = i. Symmetrically D(0,j) = j. Fill row by row and the answer waits at D(m,n).

Filling the edit-distance table for kitten to sitting

The full grid, one corner at a time

Put kitten down the left (rows 1..6) and sitting across the top (columns 1..7). Row 0 is 0 1 2 3 4 5 6 7 and column 0 is 0 1 2 3 4 5 6.

Cell D(1,1) compares k and s. They differ, so c = 1. The three candidates are diagonal 0+1, left 1+1, top 1+1. The minimum is 1.
Cell D(2,2) compares i and i. They match, so c = 0. Diagonal is D(1,1) + 0 = 1, which beats both +1 neighbours. Value 1.
The matching run itt keeps the diagonal cheap, so along that stretch the cost stays at 1 while the indices climb together.
Near the end, e versus i forces a substitution and n lines up, then the extra g in sitting forces one insert.
The bottom-right cell D(6,7) settles at 3. That is the edit distance.

The three edits recovered by traceback are: substitute k to s, substitute e to i, insert g. Every other letter is a free match along the diagonal.

The cost stays at 1 through the matching run itt, then rises as the tail letters diverge. The final answer, one cell further right, is 3.

The knapsack recurrence and a worked fill

The 0/1 knapsack packs a subset of items into a bag of capacity W to maximise total value, taking each item at most once. Let K(i, w) be the best value using the first i items within weight w. Then:

K(i,w) = \max\{ K(i-1,w),\; K(i-1,\,w - w_i) + v_i \}

The first term K(i-1,w) skips item i. The second term takes it: add its value v_i to the best packing of earlier items in the leftover space w - w_i. The "take" branch is only legal when w_i \le w. Base case: with zero items, K(0,w) = 0 for every w.

Three items, capacity 5

Items: A (weight 2, value 3), B (weight 3, value 4), C (weight 4, value 5). Capacity W = 5. Fill row by row across capacities 0..5.

Knapsack table K(i, w), best value using first i items at capacity w
items \ w	2	3	4	5
none	0	0	0	0
A only	3	3	3	3
A, B	3	4	4	7
A, B, C	3	4	5	7

Row A: item A weighs 2, so columns 2 through 5 can hold it for value 3; columns 0 and 1 stay at 0.
Cell K(2,5): skip B gives 3; take B gives 4 + K(1, 2) = 4 + 3 = 7. Max is 7, so A and B together.
Cell K(3,5): skip C keeps 7; take C gives 5 + K(2, 1) = 5 + 0 = 5. Max is 7. C loses.
The answer is 7, achieved by packing A and B (weight 5, value 7).

Reading the table and tracing the answer

A filled table hands you two things: the optimal number in one corner and the reasoning everywhere else. To recover the reasoning, walk backwards from that corner and at each cell ask which neighbour produced its value.

In edit distance, start at D(m,n). If the current value equals the diagonal plus c, that step was a match (when the letters agree) or a substitution (when they differ). If it equals the left neighbour plus 1, it was an insert. If it equals the top plus 1, a delete. Step to the winning neighbour and repeat until you reach D(0,0). Reverse the recorded steps to read the alignment.

In knapsack, start at K(n, W). If it equals K(n-1, W), item n was skipped, so move up a row at the same column. Otherwise item n was taken, so record it and move to K(n-1, W - w_n). For the table above that path is: take B (drop to column 2), take A (drop to column 0), stop. Value 7, items A and B, exactly matching the forward fill.

Traceback needs the whole table. If you compress a knapsack solver to two rows to save memory, you still get the correct final value, but you can no longer reconstruct which items were chosen without extra bookkeeping. Keep the full grid when you care about the choice, not just the score.

Common mistakes

Four errors account for most wrong tables.

Wrong base row: Forgetting that D(i,0) = i and D(0,j) = j. If you seed those with zeros, every distance comes out too small.
Fill order that reads unfilled cells: Each cell needs its diagonal, left, and top already done. Filling column-major when the recurrence expects row-major can read a blank neighbour. Respect the dependency direction.
Off-by-one on substitution cost: The diagonal cost c is 0 only when A_i = B_j, using 1-based letters against 0-based index math. Mixing the two shifts every comparison by one letter.
Reusing an item in 0/1 knapsack: The take branch must read K(i-1, w - w_i), the previous row. Reading the current row K(i, w - w_i) instead solves the unbounded knapsack, where each item can repeat. That is a different problem with a different answer.

Related tools on this site

Dynamic programming sits inside a family of algorithm visualizers here. If recursion and choice trees interest you, the Minimax Tic-Tac-Toe tool shows a game tree scored bottom-up, which is the same "solve leaves first" idea. For graph shortest paths, the Pathfinding Visualizer and the Graph Algorithm Playground run Dijkstra and breadth-first search, cousins that also build answers outward from known ones. To feel why avoiding repeated work matters, the Big-O Complexity Race puts n^2 next to 2^n. And for a contrast in strategy, the Huffman Coding Visualizer builds an optimal code greedily rather than by tabulation, while the Sorting Algorithm Visualizer shows divide-and-conquer, which splits into non-overlapping parts instead of reusing them.

Frequently asked questions

Is dynamic programming the same as recursion?

No. Recursion is one way to express the subproblem relationship, but plain recursion recomputes the same subproblem many times. Dynamic programming stores each answer once. You can implement it top-down (recursion plus a cache, called memoization) or bottom-up (filling the table in dependency order). Both produce the same numbers.

Why is edit distance sometimes called Levenshtein distance?

Levenshtein distance is the specific version where insert, delete, and substitute each cost 1. That is exactly the recurrence used here. Other edit distances change the costs or forbid substitution, which changes the numbers but not the table method.

What does a cost of 0 on the diagonal mean?

It means the two current letters match, so no edit is spent aligning them. The value simply copies the diagonal neighbour. A run of matching letters produces a stripe of equal values down the diagonal, which is why itt in the worked example held the cost flat at 1.

Can the knapsack table give a value the items cannot actually reach?

No. Every cell corresponds to a real subset that fits the weight limit, because each cell is built from a legal skip or a legal take. The final value 7 in the example is achieved by the concrete set A and B, weight 5.

How large can these tables get before they are too slow?

Edit distance runs in O(mn) time and space, so two 1000-letter strings need a million cells, which is instant. Knapsack runs in O(nW), so it scales with the numeric capacity, not just item count. A capacity of a billion breaks the method even with few items.

Try it yourself in the tool