DP on Grids

A delivery robot crosses a warehouse floor laid out as a grid. It starts in the top-left corner and must reach the loading bay in the bottom-right. The aisles are one-way, so it can only move right or down. Each cell shows how many seconds it takes to cross, because some aisles are busier than others.

A robot that always steps into the cheaper next cell goes down to the 2 (cheaper than the 3), down again to the 6 (cheaper than the 9), and along the bottom: 5 + 2 + 6 + 2 + 2 + 9 = 26 seconds. The best route goes the other way and takes 21. With 3 rows and 4 columns there are only 10 routes, so you could try them all. On a 20 by 20 floor there are more than 35 billion. You need a table.

#The five steps

This is the recipe from Introduction to Dynamic Programming with two indexes instead of one. The trick is the same as in 1D Dynamic Programming: ask about the very last move.

1. State. dp[r][c] is the fastest time to get from the start to cell (r, c), counting both the start cell and this one.
2. Recurrence. The robot entered (r, c) either from above or from the left. Whichever it was, it should have got there as fast as possible. So dp[r][c] = min(dp[r − 1][c], dp[r][c − 1]) + cost[r][c].
3. Base cases. dp[0][0] = cost[0][0]. Cells in the top row can only be entered from the left, and cells in the left column only from above, so each of those has a single option.
4. Order. Each cell reads the cell above and the cell to its left. Go row by row, left to right inside each row, and both are always ready.
5. Answer. dp[rows − 1][cols − 1], the bottom-right cell.

for r from 0 to rows - 1:  for c from 0 to cols - 1:    if r == 0 and c == 0: dp[r][c] = cost[0][0]    else if r == 0: dp[r][c] = dp[r][c-1] + cost[r][c]    else if c == 0: dp[r][c] = dp[r-1][c] + cost[r][c]    else: dp[r][c] = min(dp[r-1][c], dp[r][c-1]) + cost[r][c]return dp[rows-1][cols-1]

The table tells you the best time, not the route. To get the route, start at the bottom-right and repeatedly step to whichever of "above" or "left" holds the smaller number, as the last step of the tracer does. Reverse the cells you visited and you have the path.

#The code

function fastestRoute(cost) {
  const rows = cost.length;
  const cols = cost[0].length;
  const dp = Array.from({ length: rows }, () => new Array(cols).fill(0));
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (r === 0 && c === 0) dp[r][c] = cost[0][0];
      else if (r === 0) dp[r][c] = dp[r][c - 1] + cost[r][c];
      else if (c === 0) dp[r][c] = dp[r - 1][c] + cost[r][c];
      else dp[r][c] = Math.min(dp[r - 1][c], dp[r][c - 1]) + cost[r][c];
    }
  }
  return dp[rows - 1][cols - 1];
}
 
fastestRoute([[5, 3, 1, 6], [2, 9, 1, 5], [6, 2, 2, 9]]); // 21

def fastest_route(cost):
    rows, cols = len(cost), len(cost[0])
    dp = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                dp[r][c] = cost[0][0]
            elif r == 0:
                dp[r][c] = dp[r][c - 1] + cost[r][c]
            elif c == 0:
                dp[r][c] = dp[r - 1][c] + cost[r][c]
            else:
                dp[r][c] = min(dp[r - 1][c], dp[r][c - 1]) + cost[r][c]
    return dp[rows - 1][cols - 1]
 
fastest_route([[5, 3, 1, 6], [2, 9, 1, 5], [6, 2, 2, 9]])  # 21

#Counting routes, with one row of memory

Now some cells hold shelves and cannot be entered at all, and the question changes: how many different routes reach the bay? The five steps barely move.

• State: ways[r][c] is the number of routes from the start to (r, c).
• Recurrence: every route into a cell arrives from above or from the left, never both, so ways[r][c] = ways[r − 1][c] + ways[r][c − 1]. A shelf cell is 0.
• Base case: ways[0][0] = 1, the route of standing still. Off-grid neighbours count as 0.
• Order and answer are as before.

Here is a 3 by 4 floor with one shelf in the middle of row 1, marked ■. Each number is the count of routes to that cell:

Without the shelf there would be 10 routes. The shelf removes 6 of them, leaving 4.

Each row only reads the row above it and itself. So keep a single array ways of length cols. When you reach column c in a new row, ways[c] still holds the value from the row above, and ways[c − 1] already holds the value for the current row. Adding them is exactly the recurrence.

// grid[r][c] is 1 for a shelf, 0 for open floor.
function countRoutes(grid) {
  const cols = grid[0].length;
  const ways = new Array(cols).fill(0);
  ways[0] = 1;
  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 1) ways[c] = 0; // no route ends on a shelf
      else if (c > 0) ways[c] += ways[c - 1]; // above + left
    }
  }
  return ways[cols - 1];
}
 
countRoutes([[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 0]]); // 4

# grid[r][c] is 1 for a shelf, 0 for open floor.
def count_routes(grid):
    cols = len(grid[0])
    ways = [0] * cols
    ways[0] = 1
    for row in grid:
        for c in range(cols):
            if row[c] == 1:
                ways[c] = 0  # no route ends on a shelf
            elif c > 0:
                ways[c] += ways[c - 1]  # above + left
    return ways[cols - 1]
 
count_routes([[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 0]])  # 4

#Common mistakes

#Check yourself

#What to practise next

Grids are not always floors. In Knapsack the rows are items and the columns are amounts of space left, and in DP on Strings the rows and columns are letters of two words. The fill pattern you just used, above and to the left, carries straight over. To practise this lesson, try Snowplow to the Road for the cheapest route and Roadworks on the Grid for counting routes around blocked cells.