Deeper

Lab · c05.s05.L1

Shortest-path DP

Saving a subproblem's answer pays exactly when the same subproblem is reached many times: the work falls from the number of calls to the number of distinct cells.

Question: When does saving a result beat recomputing it?

Shortest-path DPA square grid of printed costs fills in row by row. Each cell shows the cheapest cost of reaching it from the top-left corner, and a gold line traces the cheapest path to the bottom-right corner, total 35. Two counters rise together: with saving on one stops at 36 computations, one per cell; with saving off the other reaches 923, because the bottom-right cell alone is recomputed 252 times.Shortest-path DPWhen does saving a result beat recomputing it?SavingWith savingWithout savingCells filledSaving changes the work, not the answer.large navy number: cheapest cost to reach the cell | small russet number: printed cost, not yet computed282348453399152227926134372225474599ON000 of 36Both counters count cell computations.The grid fills the same either way.
Synthetic Synthetic: the cell costs are integers drawn from seed 505, and the cheapest costs, the gold path and both call counts are exact consequences of that grid, checked against an exhaustive walk of every monotone path. The frames fill the grid from the corner outward; on the default 6×6 grid the saved counter stops at 36 computations while the unsaved counter climbs to 923.
Lab controls
6

Left/Right: step ±1; Page Up/Page Down: step ±2; Home: 4; End: 10. Changing n restarts the fill.

On

Space toggles saving on and off; the checkbox is a normal tab stop. Changing it restarts the fill.

600 ms per step

Left/Right: ±120 ms; Page Up/Page Down: ±240 ms; Home: 120; End: 1200

Frame 1 of 6: 0 of 36: nothing computed yetNo cell is computed yet: the grid shows the 36 printed costs and both counters read 0. With saving on, each cell will be computed exactly once.

Keyboard: Space plays or pauses, Left and Right step, Home goes to the first frame, End goes to the last frame.

Text description of this lab

A square grid of printed costs fills in row by row. Each cell shows the cheapest cost of reaching it from the top-left corner, and a gold line traces the cheapest path to the bottom-right corner, total 35. Two counters rise together: with saving on one stops at 36 computations, one per cell; with saving off the other reaches 923, because the bottom-right cell alone is recomputed 252 times.

Return to the section that hosts this lab

Caption status: synthetic. Every lab declares one of published, re-simulated, schematic, synthetic or interpolated.