DP on a Grid
Dynamic programming is a table where every cell is an answer to a smaller version of the question. Name the state, decide the base cases you know for free, write the rule that builds a cell from cells already filled, and fill the table in an order where that is always true. On a grid the state is a cell, the rule reads the cell above and the cell to the left, and row by row is the order.
Each cell has a cost. Find the cheapest path from the top-left to the bottom-right moving only down or right. The table is filled in place: each cell becomes the cheapest total to reach it, which is its own cost plus the cheaper of the two ways in.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 4, with their answers.
(1, 1) costs 5. Above totals 4, left totals 2. What goes here?
Answer: 7. Own cost plus the cheaper way in: 5 + min(4, 2) = 7. The dearer way can never be part of a cheapest path.
(1, 2) costs 1. Above totals 5, left totals 7. What goes here?
Answer: 6. Own cost plus the cheaper way in: 1 + min(5, 7) = 6. The dearer way can never be part of a cheapest path.
(2, 1) costs 2. Above totals 7, left totals 6. What goes here?
Answer: 8. Own cost plus the cheaper way in: 2 + min(7, 6) = 8. The dearer way can never be part of a cheapest path.
(2, 2) costs 1. Above totals 6, left totals 8. What goes here?
Answer: 7. Own cost plus the cheaper way in: 1 + min(6, 8) = 7. The dearer way can never be part of a cheapest path.
How it runs, step by step
Each cell has a cost. Find the cheapest path from the top-left to the bottom-right moving only down or right. The table is filled in place: each cell becomes the cheapest total to reach it, which is its own cost plus the cheaper of the two ways in.
Finding the minimum path sum on a 3 by 3 grid, replacing each cost with the cheapest total to reach that cell.
(0, 0) is the start. Its cheapest total is its own cost, 1.
Cell 0, 0 becomes 1.
(0, 1) on the top row can only be entered from the left: 3 + 1 = 4.
Cell 0, 1 becomes 4.
(0, 2) on the top row can only be entered from the left: 1 + 4 = 5.
Cell 0, 2 becomes 5.
(1, 0) on the left column can only be entered from above: 1 + 1 = 2.
Cell 1, 0 becomes 2.
(1, 1) costs 5. Coming from above totals 4, from the left 2. Take the cheaper: 5 + min(4, 2) = 7. The cheapest way here must end with the cheapest way to one of those two cells.
Cell 1, 1 becomes 7.
(1, 2) costs 1. Coming from above totals 5, from the left 7. Take the cheaper: 1 + min(5, 7) = 6. The cheapest way here must end with the cheapest way to one of those two cells.
Cell 1, 2 becomes 6.
(2, 0) on the left column can only be entered from above: 4 + 2 = 6.
Cell 2, 0 becomes 6.
(2, 1) costs 2. Coming from above totals 7, from the left 6. Take the cheaper: 2 + min(7, 6) = 8. The cheapest way here must end with the cheapest way to one of those two cells.
Cell 2, 1 becomes 8.
(2, 2) costs 1. Coming from above totals 6, from the left 8. Take the cheaper: 1 + min(6, 8) = 7. The cheapest way here must end with the cheapest way to one of those two cells.
Cell 2, 2 becomes 7.
Minimum path sum 7. Walking back from the corner along the cheaper neighbour recovers the path itself. 9 cells, each computed once from two known cells: O(rows x cols).
The minimum path sum is 7. The cheapest path is highlighted.
Remember
- State: what identifies a subproblem. Here a cell (r, c). The table has one entry per state.
- Base cases seed the table. Transition builds each cell from cells already computed. Tabulation is filling in an order that guarantees that.
- Optimal substructure: the best path to a cell ends with the best path to one of its neighbours, so keeping only the best per cell loses nothing.
Topics covered
What the words mean
- Optimal Substructure
- An optimal solution is built from optimal solutions of subproblems.
- Recurrence
- Defining a value in terms of smaller instances of the same problem.
- State
- The minimal parameters that identify a subproblem; they become the table's dimensions.
- Transition
- The rule that computes one state from earlier states.
Where this is used
Developer toolsdiff and git diff
Comparing two files means comparing every prefix of one against every prefix of the other, which is a grid with one cell per pair of prefixes. Each cell holds the cheapest edit script reaching it, built from three neighbours: a deletion from above, an insertion from the left, or a matching line from the diagonal. Walking the finished table backwards is what turns one distance number into the plus and minus hunks you actually read. Production implementations like Myers' algorithm search that same grid more cleverly instead of filling all of it, but the grid is still the model.
GraphicsSeam carving in image editors
Content-aware resizing narrows a photo by deleting a connected top-to-bottom seam of unimportant pixels instead of squashing the whole image. The table is the image: cell (r, c) is the cheapest seam ending at that pixel, its own energy plus the minimum of the three pixels above it. That is min-path-sum on a pixel grid, filled row by row and then traced back from the smallest value in the bottom row. It ships as Content-Aware Scale in Photoshop and as the Liquid Rescale plugin for GIMP.
NetworkingViterbi decoding in Wi-Fi and GSM
A convolutional code turns a noisy bit stream into a grid with one column per received symbol and one row per encoder state. Each cell keeps the most likely path into that state and depends only on the previous column, so a decoder can fill one column per symbol at line rate and trace back the single surviving path at the end. 802.11a/g and GSM both specify convolutional codes decoded this way, which is why the silicon is a fixed grid of add-compare-select units rather than a general processor.
BioinformaticsSequence alignment in genomics
Smith-Waterman aligns two DNA or protein sequences by filling a grid where cell (i, j) scores the best local alignment ending at residue i of one sequence and residue j of the other, taking a match or mismatch from the diagonal, a gap from above or from the left, and 0 when every option would score negative. That 0 floor is what makes it local: the answer is the highest cell anywhere in the table rather than the bottom right corner, and the traceback starts there. It is the exact answer where BLAST is a fast heuristic, so it is what tools such as EMBOSS water run when the alignment has to be right. The work is exactly rows x cols cells under one fixed rule, which is why it is a standard target for SIMD and FPGA acceleration.
Why it works this way
Why row by row, and which fill orders break
The transition reads the cell above and the cell to the left, so both have to already hold their final value when you touch a cell. Left to right within a row, top to bottom across rows, guarantees that; column by column happens to work here too. Any order that reaches a cell before its two inputs are written reads a leftover zero and returns a wrong answer with nothing to crash on. The rule behind the rule is that the fill order must be a topological order of the arrows the transition draws.
Why build a table instead of just recursing?
The plain recursion countPaths(r, c) = countPaths(r - 1, c) + countPaths(r, c - 1) is correct, but every leaf call contributes exactly 1 to the answer, so the number of leaf calls is the answer itself. On an 18 x 18 grid that is 2,333,606,220 leaf calls to compute 324 distinct cells. Memoising the recursion fixes it and ends up filling the same table; tabulation fills it directly and skips the call stack. Incidentally that same number no longer fits in a 32-bit Int, which is why path-counting problems usually cap the grid or ask for the count modulo a prime.
Base cases are the edges, not a row of zeros
A cell in the top row has no cell above it and a cell in the left column has nothing to its left, so the transition cannot run there at all. Treating the missing neighbour as 0 is fine for counting, where zero ways in is the truth, and wrong for min-path-sum, where it lets every top row cell ignore everything to its left, so reaching one appears to cost nothing but its own value. Obstacles split the same way: a blocked cell is 0 when counting paths but has to be infinity when minimising, because 0 would make the wall the cheapest route through the grid.
One row of memory is enough, and what that costs
Each cell reads only the row above and the cell to its left, so a single array of cols entries carries everything. Sweeping left to right, dp[c] still holds the row above at the moment you read it, and dp[c - 1] already holds the current row. Space drops from rows x cols to cols, which matters once the grid is an image or a pair of long strings. The price is that you no longer have the filled table, so you can report the best value but cannot walk backwards through it to recover the path that achieved it.
Read more
- Dynamic programmingWikipedia
- Levenshtein distanceWikipedia
- Seam carvingWikipedia
- Introduction to dynamic programmingUSACO Guide
- Grid Paths ICSES 1638 · cses.fi