Lesson 29.1 · DP on Grids

Counting and Costing Paths

If moves are right and down, a cell is reached from above or from the left: dp[r][c] = combine(dp[r − 1][c], dp[r][c − 1]).

14 min

Think of it like this

A city laid out in blocks where you may only walk east or south. The number of routes to a corner is the routes to the corner above plus the routes to the corner on the left.

1.Fill row by row

Count paths: dp[r][c] = dp[r − 1][c] + dp[r][c − 1], with the first row and column all 1 (only one way along an edge). Obstacles set their cell to 0.

Cheapest path: dp[r][c] = grid[r][c] + min(dp[r − 1][c], dp[r][c − 1]). Same order, min instead of sum.

Filling row by row guarantees the cell above and the cell to the left are ready when you need them.

Main.java

public class Main {
    public static void main(String[] args) {
        int m = 3, n = 4;
        int[][] dp = new int[m][n];
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                dp[r][c] = (r == 0 || c == 0) ? 1 : dp[r - 1][c] + dp[r][c - 1];
        for (int[] row : dp) {
            StringBuilder sb = new StringBuilder();
            for (int x : row) sb.append(x).append(' ');
            System.out.println(sb.toString().trim());
        }
        System.out.println("paths = " + dp[m - 1][n - 1]);
    }
}

Output

▶ Dry run: Unique paths in a 3 × 4 gridm = 3, n = 4

Step 1/4First row and first column: exactly one path each (all right or all down).

Remember

State = cell; transition = where you came from.
Fill in an order that makes predecessors ready.
Count: +. Cost: min/max.

Common mistakes

Initialising the first row as all 1 even when an obstacle blocks part of it.

Command Palette

Counting and Costing Paths

1.Fill row by row