When two indices are needed
Some problems track two changing quantities at once, so the natural state is a grid dp at row and column. Counting paths through a grid, minimum path sum, and edit distance all use a two dimensional table.
The recurrence
In unique paths, a cell can be reached only from above or from the left, so dp at i and j equals dp at i minus one and j plus dp at i and j minus one. Minimum path sum replaces addition of counts with a minimum of incoming costs plus the current cell.
- Decide what each axis means, for example position in two sequences.
- Express each cell from its neighbors, usually up, left, or the diagonal.
- Initialize the first row and column as base cases.
Filling order
Process rows top to bottom and columns left to right so every neighbor a cell depends on is already computed. The table holds one entry per cell, and each entry costs constant work.
Key idea
Grid DP indexes a table by two coordinates and computes each cell from a few neighbors, so problems involving two interacting positions become an orderly sweep across the grid.