DP on Grids

The Idea

A grid makes DP two-dimensional. When movement is limited to right and down, a cell can only be entered from above or from the left, so its answer combines just those two. Counting routes means adding them together; finding the cheapest route means taking the smaller one and adding the cell's own cost.

Real-World Example

A hiker crossing a valley mapped into squares, each labelled with the metres of climb it costs. Walking only east or south, the least exhausting crossing is worked out square by square: each square's running total is its own climb plus the gentler of the two ways into it.

The Code

grid = [[1, 3, 1],
        [1, 5, 1],
        [4, 2, 1]]

cost = [row[:] for row in grid]
for i in range(len(grid)):
    for j in range(len(grid[0])):
        if i or j:                                        # skip the start cell
            above = cost[i - 1][j] if i else float("inf")
            left = cost[i][j - 1] if j else float("inf")
            cost[i][j] += min(above, left)                # cheapest way in

print(cost[-1][-1])   # 7

grid = [[1, 2, 3],
      [4, 5, 6]]

cost = [row[:] for row in grid]
for i in range(2):
  for j in range(3):
      if i or j:
          above = cost[i - 1][j] if i else 10 ** 9
          left = cost[i][j - 1] if j else 10 ** 9
          cost[i][j] += min(above, left)

print(cost[1][2])