Skip to content
Tutorials Center
My learning

Topics

Lesson 155 of 225 ยท Dynamic Programming

DP on Grids

Learn grid dynamic programming in Python: unique paths, minimum path sum, obstacles, maximal square and the dungeon game, from brute force to DP.

A grid is the friendliest place to learn dynamic programming. The state is just a pair of coordinates (row, col), the table is the grid itself, and the order of filling is obvious: top to bottom, left to right. Problems like "how many ways to walk from the top-left to the bottom-right corner" or "what is the cheapest route" all share one shape.

In this lesson you will solve five grid problems that cover the pattern: unique paths, minimum path sum, paths with obstacles, the largest square of ones, and the dungeon game, where you must fill the table backwards. If you want a refresher on turning recursion into a table first, read memoization vs tabulation.

The pattern

When you may only move right or down, the cell (r, c) can only be reached from the cell above (r-1, c) or the cell to the left (r, c-1). So the answer for a cell is built from those two neighbors:

TEXT
          col 0   col 1   col 2
row 0   [ start ]->[  a  ]->[  b  ]
            |         |        |
            v         v        v
row 1   [  c  ]->[ (r,c)]->[  d  ]
                    ^ comes from the cell above and the cell to its left

Steps for every grid DP:

  1. State: dp[r][c] = the best answer for the subproblem ending (or starting) at (r, c).
  2. Transition: combine the cell above and the cell to the left.
  3. Base cases: the first row and first column, which have only one possible predecessor.
  4. Order: an order where both predecessors are done first (row by row works).
  5. Answer: usually the opposite corner.

Unique paths

Problem. A robot starts at the top-left of an m x n grid and may move only right or down. How many different paths lead to the bottom-right corner?

Brute force. Recurse: paths from (r, c) equal paths from (r+1, c) plus paths from (r, c+1). It is correct but recomputes cells again and again, giving about 2^(m+n) calls.

DP. Count paths into each cell: dp[r][c] = dp[r-1][c] + dp[r][c-1], with the first row and column all 1 (only one way to reach them).

TEXT
3 x 4 grid:
  1   1   1   1
  1   2   3   4
  1   3   6  10     <- 10 paths to the corner
Python Unique paths: brute force vs DP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The DP costs O(m x n) time. Since row r needs only row r - 1, a single row of length n is enough: update it in place with row[c] += row[c-1], giving O(n) space. There is also a closed form from combinatorics: you make m - 1 down moves and n - 1 right moves in any order, so the count is C(m + n - 2, m - 1).

Python One-row version and the formula

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Unique paths with obstacles

Some cells are blocked (1 in the grid). A blocked cell has zero paths into it, and paths cannot pass through it. Everything else follows the same rule.

Watch the first row and column: once a blocked cell appears, every cell after it in that row (or column) is unreachable, so the "all ones" base case no longer holds. Handling the base cases inside the loop avoids the trap.

Python Unique paths with obstacles

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Minimum path sum

Problem. Each cell has a cost. Moving only right or down from the top-left to the bottom-right, find the path with the smallest total cost.

State. dp[r][c] = the cheapest cost to reach (r, c), including that cell's own cost.

Transition. dp[r][c] = cost[r][c] + min(dp[r-1][c], dp[r][c-1]). On the first row you can only come from the left; on the first column only from above.

TEXT
cost grid          dp (cheapest cost to reach each cell)
 1  3  1            1   4   5
 1  5  1            2   7   6
 4  2  1            6   8   7     <- answer 7

The cheapest route is 1 -> 3 -> 1 -> 1 -> 1, visiting the top row then the right column.

Python Minimum path sum with the route

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(m x n), space O(m x n) (or O(n) if you only need the number). Because the grid is read-only in many interview versions, a rolling row is the polite way to save space.

Maximal square

Problem. A grid of 0s and 1s. Find the area of the largest square made only of 1s.

Brute force. For every cell as a top-left corner, grow the square while all cells inside are 1. That is about O((m x n) x min(m, n)^2) if you recheck each square, far too slow for large grids.

DP. Let dp[r][c] be the side length of the largest all-ones square whose bottom-right corner is (r, c). If the cell is 1:

TEXT
dp[r][c] = 1 + min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1])

The three neighbors limit how far the square can grow: the smallest of them is the largest square that fits on all three sides. If the cell is 0, dp[r][c] = 0.

TEXT
input         dp
1 0 1 1       1 0 1 1
1 1 1 1       1 1 1 2
1 1 1 1       1 2 2 2    <- the 2s mark 2 x 2 squares
Python Largest square of ones

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This runs in O(m x n) time. Moving in any direction, not just right and down, makes a grid a graph instead, so use BFS or Dijkstra there. DP needs the "only forward" structure.

The dungeon game: filling backwards

Problem. A knight starts at the top-left of a dungeon and must reach the princess at the bottom-right, moving only right or down. Each cell changes health by its value (negative = damage, positive = potion). Health must stay at least 1 at all times. What is the minimum starting health?

A forward DP fails here: the best prefix is not the one with the largest sum, because a low point later may need a big reserve earlier. Instead define the state from the end:

need[r][c] = the minimum health required on entering (r, c) to survive to the end.

TEXT
need[r][c] = max(1, min(need[r+1][c], need[r][c+1]) - dungeon[r][c])

Start from the princess's cell and fill toward the top-left.

Python Dungeon game (backward DP)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The answer for this dungeon is 7: go right, right, down, down, taking -2, -3, 3, 1, -5, and your health never drops below 1.

Choosing the order

  • Forward (cells depend on up and left): unique paths, min path sum, maximal square.
  • Backward (cells depend on down and right): dungeon game, and any "start from the end" definition.
  • Memoized recursion is just as valid and is easier when blocked cells or irregular moves mean not every cell is needed.

Add diagonal or extra moves by adding more predecessors to the transition, as maximal square does with (r-1, c-1).

Common mistakes

  • Index out of range on the first row/column. Guard r > 0 and c > 0, or pad the table with an extra row and column of sentinels.
  • Writing [[0] * n] * m. All rows then alias one list. Use a comprehension.
  • Forgetting that a blocked start cell makes the answer 0.
  • Using the wrong "no path" value. Use infinity for minimums and 0 for counts.
  • Applying right/down DP to grids that allow moving up or left. Cycles appear; use graph search.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many right/down paths are there in a 3 x 4 grid (3 rows, 4 columns)?

    The DP table's corner is 10, which equals C(3 + 4 - 2, 3 - 1) = C(5, 2).
  2. 2. In maximal square, what does dp[r][c] store?

    Fixing the bottom-right corner lets the three neighbors (up, left, diagonal) bound the square, giving 1 + min of them.
  3. 3. Why is the dungeon game filled from the bottom-right to the top-left?

    Survival depends on the future path. Defining need[r][c] as the health required on entry to reach the end makes each cell depend on cells to its right and below.
  4. 4. What is the time complexity of the grid DPs in this lesson for an m x n grid?

    Each cell is computed once from a constant number of neighbors.
  5. 5. In unique paths with obstacles, what is wrong with setting the entire first row to 1 first?

    Cells after a blocked cell in the first row have no way in, so they must be 0, not 1.

Summary

  • Grid DP states are coordinates; each cell is built from a few neighbors in an order that finishes the neighbors first.
  • Unique paths: dp[r][c] = dp[r-1][c] + dp[r][c-1]. Min path sum: add the cell cost to the smaller predecessor. Obstacles are 0 paths.
  • Maximal square: 1 + min(up, left, diagonal) on ones, 0 on zeros.
  • Define the state from the end when the future decides the answer, as in the dungeon game.
  • Time O(m x n); a rolling row often cuts the space to O(n).
  • If moves can go in all four directions, it is a graph problem, not a DP table.

Next: DP on Strings