Grid Path Tabulation

Foundations

Two-dimensional DP stores answers in a table dp[r][c], one per pair of indexes, and builds each cell from neighbors already solved. It is 1D tabulation with a second index: a definition of dp[r][c], a recurrence over earlier cells, base cases along the edges, and a fill order that solves every neighbor first. When moves go only right or down, filling row by row, left to right, does exactly that.

A cell's top and left neighbors are the only cells a right-or-down path can come from. So a count of paths adds them, dp[r][c] = dp[r - 1][c] + dp[r][c - 1], while a best total takes the better of the two plus the cell's own value. The first row and column have one neighbor each, so they are filled first, and the answer waits in the bottom-right corner.

Take grid = [[7, 1, 5], [3, 6, 2]] and find the largest sum of a right-or-down path from the top-left corner. The first row accumulates to 7, 8, 13 and the first column to 7, 10. Then 6 adds max(8, 10) for 16, and 2 adds max(13, 16) for 18: the path 7, 3, 6, 2.

• Bottom-Up Tabulation

  That lesson filled a table one index at a time. This one adds a second index.

  Open lesson

Case Scenario

Unique Paths counts the right-or-down paths through an m × n grid from the top-left cell to the bottom-right. Every path into a cell arrives from above or from the left, so dp[r][c] = dp[r - 1][c] + dp[r][c - 1], and the first row and column hold 1. For m = 3 and n = 4, the corner holds 10.

The direct approach recurses: the paths from a cell are the paths going down plus the paths going right. The same cells are reached by many routes, so their counts are recomputed every time, and the calls grow exponentially, about 2^(m + n), though the grid has only m · n distinct cells.