Understanding the grid DP pattern

A large family of problems asks us to move across a grid cell by cell, optimising a route or counting routes through it. Counting the ways to walk from one corner of a grid to the opposite corner, finding the cheapest path across a field of tolls, or measuring the largest solid block of marked cells are all of this kind where we work over a two-dimensional matrix, and the answer we want at any cell is built directly from the answers at a few cells next to it.

Problems like these are solved by the grid DP technique, where every cell of the board marks a subproblem, we solve the subproblems in an order that respects how the cells depend on one another, and the value at each cell is built from its neighbours. Because the grid is just a two-dimensional table of states, the technique is a natural extension of the one-dimensional sequence DP we learned earlier.

The input here is always a 2D matrix, a rectangle of cells indexed by a row r and a column c. From here on we use an n x m grid as our example, with rows running 0, 1, ..., n-1 and columns 0, 1, ..., m-1.

In this lesson we will learn the grid DP technique, why it qualifies as a dynamic programming problem, and how to solve it both top-down and bottom-up.

The grid DP technique

Every grid DP problem is an instantiation of the Bellman optimality equation, and to write that equation we first fix its main components, the action set, the cost function, and the transition function. Everything else, the recurrence, the dependency order, and the target state, follows from them.