PK

PKBytes

Explore tracks
Chapter 10: Matrices, Grids and Multidimensional Arrays
10.07Beginner / Intermediate5 topics16 min4 interactive animations

Grid DP introduction

Grid dynamic programming fills a table where each cell depends on cells above and to the left: minimum path sum, counting unique paths (with and without obstacles), the maximal square and memoised recursion on a grid.

Learning goals

  • Define the DP state and recurrence for grid problems
  • Fill the table in the right order
  • Handle obstacles and borders
  • Relate memoisation to the bottom-up table

Prerequisites

Neighbourhood reasoningRecursion basics
10.07.1

Minimum path sum

Find the cheapest path from the top-left to the bottom-right moving only right or down. Let dp[r][c] be the cheapest cost to reach (r, c); it is g[r][c] plus the cheaper of coming from above or from the left. First row and column have only one predecessor. O(R·C) time; one rolling row reduces space to O(C).

Fill the table for the default 3 × 3 grid and read the answer from the last cell.

Java
1static int minPathSum(int[][] g) {
2    int R = g.length, C = g[0].length;
3    int[][] dp = new int[R][C];
4    for (int r = 0; r < R; r++)
5        for (int c = 0; c < C; c++) {
6            if (r == 0 && c == 0) dp[r][c] = g[0][0];
7            else dp[r][c] = g[r][c] + Math.min(r > 0 ? dp[r - 1][c] : Integer.MAX_VALUE, c > 0 ? dp[r][c - 1] : Integer.MAX_VALUE);
8        }
9    return dp[R - 1][C - 1];
10}

Grid dynamic programming (paths and squares)

Interactive · edit the input

Your input

Try

grid · 3 × 3

012
0
1
3
1
1
1
5
1
2
4
2
1
Cell being computedComputedCells it depends on
Setup

Minimum path sum. The grid is shown first; the table below fills in row by row, each cell from cells above and to the left.

Step 1 / 11
Java
1// minimum path sum, moving only right or down
2dp[0][0] = g[0][0];
3for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) {
4    if (r == 0 && c == 0) continue;
5    int best = Math.min(r > 0 ? dp[r - 1][c] : INF, c > 0 ? dp[r][c - 1] : INF);
6    dp[r][c] = g[r][c] + best;
7}
8// unique paths: dp[r][c] = dp[r - 1][c] + dp[r][c - 1], with dp[0][*] = dp[*][0] = 1; obstacles force 0
9dp[r][c] = g[r][c] == 1 ? 0 : (r > 0 ? dp[r - 1][c] : 0) + (c > 0 ? dp[r][c - 1] : 0);
10// largest square of 1s: dp = side of the biggest square whose bottom-right corner is (r, c)
11dp[r][c] = g[r][c] == 0 ? 0 : 1 + Math.min(dp[r - 1][c], Math.min(dp[r][c - 1], dp[r - 1][c - 1]));
12return dp[R - 1][C - 1];                       // maximal square: the largest dp value, squared

Live state

R

3

C

3

No condition evaluated on this step
Execution trace (dry run table)Show 11 steps
StepLineStateWhat happens
1L2R=3 C=3Minimum path sum. The grid is shown first; the table below fills in row by row, each cell from cells above and to the left.
2L6r=0 c=0 dp[0][0]=1dp[0][0]: the start costs 1.
3L6r=0 c=1 dp[0][1]=4dp[0][1]: 3 + min(n/a, 1) = 4.
4L6r=0 c=2 dp[0][2]=5dp[0][2]: 1 + min(n/a, 4) = 5.
5L6r=1 c=0 dp[1][0]=2dp[1][0]: 1 + min(1, n/a) = 2.
6L6r=1 c=1 dp[1][1]=7dp[1][1]: 5 + min(4, 2) = 7.
7L6r=1 c=2 dp[1][2]=6dp[1][2]: 1 + min(5, 7) = 6.
8L6r=2 c=0 dp[2][0]=6dp[2][0]: 4 + min(2, n/a) = 6.
9L6r=2 c=1 dp[2][1]=8dp[2][1]: 2 + min(7, 6) = 8.
10L6r=2 c=2 dp[2][2]=7dp[2][2]: 1 + min(6, 8) = 7.
11L12return=7Answer 7 (the cheapest path cost). 9 cells, O(1) each: O(R x C) time and space (O(C) with a rolling row).
10.07.2

Unique paths

Count the paths from the top-left to the bottom-right moving right or down. Every cell can be reached from above or from the left, so dp[r][c] = dp[r-1][c] + dp[r][c-1], with 1 along the first row and column. The answer for an R × C grid is also the binomial coefficient C(R + C - 2, R - 1). Counts grow fast, so use long, or the modulus the problem demands.

Choose Unique paths and compare the 3 × 4 result with the formula.

Java
1static long uniquePaths(int R, int C) {
2    long[][] dp = new long[R][C];
3    for (int r = 0; r < R; r++)
4        for (int c = 0; c < C; c++)
5            dp[r][c] = (r == 0 || c == 0) ? 1 : dp[r - 1][c] + dp[r][c - 1];
6    return dp[R - 1][C - 1];
7}

Grid dynamic programming (paths and squares)

Interactive · edit the input

Your input

Try

grid · 3 × 3

012
0
1
3
1
1
1
5
1
2
4
2
1
Cell being computedComputedCells it depends on
Setup

Minimum path sum. The grid is shown first; the table below fills in row by row, each cell from cells above and to the left.

Step 1 / 11
Java
1// minimum path sum, moving only right or down
2dp[0][0] = g[0][0];
3for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) {
4    if (r == 0 && c == 0) continue;
5    int best = Math.min(r > 0 ? dp[r - 1][c] : INF, c > 0 ? dp[r][c - 1] : INF);
6    dp[r][c] = g[r][c] + best;
7}
8// unique paths: dp[r][c] = dp[r - 1][c] + dp[r][c - 1], with dp[0][*] = dp[*][0] = 1; obstacles force 0
9dp[r][c] = g[r][c] == 1 ? 0 : (r > 0 ? dp[r - 1][c] : 0) + (c > 0 ? dp[r][c - 1] : 0);
10// largest square of 1s: dp = side of the biggest square whose bottom-right corner is (r, c)
11dp[r][c] = g[r][c] == 0 ? 0 : 1 + Math.min(dp[r - 1][c], Math.min(dp[r][c - 1], dp[r - 1][c - 1]));
12return dp[R - 1][C - 1];                       // maximal square: the largest dp value, squared

Live state

R

3

C

3

No condition evaluated on this step
Execution trace (dry run table)Show 11 steps
StepLineStateWhat happens
1L2R=3 C=3Minimum path sum. The grid is shown first; the table below fills in row by row, each cell from cells above and to the left.
2L6r=0 c=0 dp[0][0]=1dp[0][0]: the start costs 1.
3L6r=0 c=1 dp[0][1]=4dp[0][1]: 3 + min(n/a, 1) = 4.
4L6r=0 c=2 dp[0][2]=5dp[0][2]: 1 + min(n/a, 4) = 5.
5L6r=1 c=0 dp[1][0]=2dp[1][0]: 1 + min(1, n/a) = 2.
6L6r=1 c=1 dp[1][1]=7dp[1][1]: 5 + min(4, 2) = 7.
7L6r=1 c=2 dp[1][2]=6dp[1][2]: 1 + min(5, 7) = 6.
8L6r=2 c=0 dp[2][0]=6dp[2][0]: 4 + min(2, n/a) = 6.
9L6r=2 c=1 dp[2][1]=8dp[2][1]: 2 + min(7, 6) = 8.
10L6r=2 c=2 dp[2][2]=7dp[2][2]: 1 + min(6, 8) = 7.
11L12return=7Answer 7 (the cheapest path cost). 9 cells, O(1) each: O(R x C) time and space (O(C) with a rolling row).
10.07.3

Obstacles

With obstacles, a blocked cell has zero paths through it, so set dp to 0 there and let every other cell sum its two predecessors; if the start or the goal is blocked the answer is 0. The first row and column stay 1 only until the first obstacle, after which they are 0.

Run the preset with an obstacle in the middle.

Java
1static long pathsWithObstacles(int[][] g) {                    // 1 = obstacle
2    int R = g.length, C = g[0].length;
3    long[][] dp = new long[R][C];
4    for (int r = 0; r < R; r++)
5        for (int c = 0; c < C; c++) {
6            if (g[r][c] == 1) { dp[r][c] = 0; continue; }
7            if (r == 0 && c == 0) dp[r][c] = 1;
8            else dp[r][c] = (r > 0 ? dp[r - 1][c] : 0) + (c > 0 ? dp[r][c - 1] : 0);
9        }
10    return dp[R - 1][C - 1];
11}

Grid dynamic programming (paths and squares)

Interactive · edit the input

Your input

Try

grid · 3 × 3

012
0
1
3
1
1
1
5
1
2
4
2
1
Cell being computedComputedCells it depends on
Setup

Minimum path sum. The grid is shown first; the table below fills in row by row, each cell from cells above and to the left.

Step 1 / 11
Java
1// minimum path sum, moving only right or down
2dp[0][0] = g[0][0];
3for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) {
4    if (r == 0 && c == 0) continue;
5    int best = Math.min(r > 0 ? dp[r - 1][c] : INF, c > 0 ? dp[r][c - 1] : INF);
6    dp[r][c] = g[r][c] + best;
7}
8// unique paths: dp[r][c] = dp[r - 1][c] + dp[r][c - 1], with dp[0][*] = dp[*][0] = 1; obstacles force 0
9dp[r][c] = g[r][c] == 1 ? 0 : (r > 0 ? dp[r - 1][c] : 0) + (c > 0 ? dp[r][c - 1] : 0);
10// largest square of 1s: dp = side of the biggest square whose bottom-right corner is (r, c)
11dp[r][c] = g[r][c] == 0 ? 0 : 1 + Math.min(dp[r - 1][c], Math.min(dp[r][c - 1], dp[r - 1][c - 1]));
12return dp[R - 1][C - 1];                       // maximal square: the largest dp value, squared

Live state

R

3

C

3

No condition evaluated on this step
Execution trace (dry run table)Show 11 steps
StepLineStateWhat happens
1L2R=3 C=3Minimum path sum. The grid is shown first; the table below fills in row by row, each cell from cells above and to the left.
2L6r=0 c=0 dp[0][0]=1dp[0][0]: the start costs 1.
3L6r=0 c=1 dp[0][1]=4dp[0][1]: 3 + min(n/a, 1) = 4.
4L6r=0 c=2 dp[0][2]=5dp[0][2]: 1 + min(n/a, 4) = 5.
5L6r=1 c=0 dp[1][0]=2dp[1][0]: 1 + min(1, n/a) = 2.
6L6r=1 c=1 dp[1][1]=7dp[1][1]: 5 + min(4, 2) = 7.
7L6r=1 c=2 dp[1][2]=6dp[1][2]: 1 + min(5, 7) = 6.
8L6r=2 c=0 dp[2][0]=6dp[2][0]: 4 + min(2, n/a) = 6.
9L6r=2 c=1 dp[2][1]=8dp[2][1]: 2 + min(7, 6) = 8.
10L6r=2 c=2 dp[2][2]=7dp[2][2]: 1 + min(6, 8) = 7.
11L12return=7Answer 7 (the cheapest path cost). 9 cells, O(1) each: O(R x C) time and space (O(C) with a rolling row).
10.07.4

Maximum square

To find the largest square made only of 1s, let dp[r][c] be the side of the largest square whose bottom-right corner is (r, c). If the cell is 0 the value is 0; otherwise it is 1 + the minimum of the three neighbours above, to the left and diagonally above-left, because the square is limited by the shortest of those. The answer is the largest dp value squared. O(R·C).

Choose Maximal square in the animation.

Java
1static int maximalSquare(int[][] g) {
2    int R = g.length, C = g[0].length, best = 0;
3    int[][] dp = new int[R][C];
4    for (int r = 0; r < R; r++)
5        for (int c = 0; c < C; c++) {
6            if (g[r][c] == 0) continue;
7            dp[r][c] = (r == 0 || c == 0) ? 1 : 1 + Math.min(dp[r - 1][c], Math.min(dp[r][c - 1], dp[r - 1][c - 1]));
8            best = Math.max(best, dp[r][c]);
9        }
10    return best * best;
11}

Grid dynamic programming (paths and squares)

Interactive · edit the input

Your input

Try

grid · 3 × 3

012
0
1
3
1
1
1
5
1
2
4
2
1
Cell being computedComputedCells it depends on
Setup

Minimum path sum. The grid is shown first; the table below fills in row by row, each cell from cells above and to the left.

Step 1 / 11
Java
1// minimum path sum, moving only right or down
2dp[0][0] = g[0][0];
3for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) {
4    if (r == 0 && c == 0) continue;
5    int best = Math.min(r > 0 ? dp[r - 1][c] : INF, c > 0 ? dp[r][c - 1] : INF);
6    dp[r][c] = g[r][c] + best;
7}
8// unique paths: dp[r][c] = dp[r - 1][c] + dp[r][c - 1], with dp[0][*] = dp[*][0] = 1; obstacles force 0
9dp[r][c] = g[r][c] == 1 ? 0 : (r > 0 ? dp[r - 1][c] : 0) + (c > 0 ? dp[r][c - 1] : 0);
10// largest square of 1s: dp = side of the biggest square whose bottom-right corner is (r, c)
11dp[r][c] = g[r][c] == 0 ? 0 : 1 + Math.min(dp[r - 1][c], Math.min(dp[r][c - 1], dp[r - 1][c - 1]));
12return dp[R - 1][C - 1];                       // maximal square: the largest dp value, squared

Live state

R

3

C

3

No condition evaluated on this step
Execution trace (dry run table)Show 11 steps
StepLineStateWhat happens
1L2R=3 C=3Minimum path sum. The grid is shown first; the table below fills in row by row, each cell from cells above and to the left.
2L6r=0 c=0 dp[0][0]=1dp[0][0]: the start costs 1.
3L6r=0 c=1 dp[0][1]=4dp[0][1]: 3 + min(n/a, 1) = 4.
4L6r=0 c=2 dp[0][2]=5dp[0][2]: 1 + min(n/a, 4) = 5.
5L6r=1 c=0 dp[1][0]=2dp[1][0]: 1 + min(1, n/a) = 2.
6L6r=1 c=1 dp[1][1]=7dp[1][1]: 5 + min(4, 2) = 7.
7L6r=1 c=2 dp[1][2]=6dp[1][2]: 1 + min(5, 7) = 6.
8L6r=2 c=0 dp[2][0]=6dp[2][0]: 4 + min(2, n/a) = 6.
9L6r=2 c=1 dp[2][1]=8dp[2][1]: 2 + min(7, 6) = 8.
10L6r=2 c=2 dp[2][2]=7dp[2][2]: 1 + min(6, 8) = 7.
11L12return=7Answer 7 (the cheapest path cost). 9 cells, O(1) each: O(R x C) time and space (O(C) with a rolling row).
10.07.5

Grid memoization

Top-down DP writes the recurrence as a recursive function and caches each (r, c) result in a table so it is computed once. It visits only the cells that are actually needed and is easier to write when the order is awkward, but recursion depth can reach R + C and each call has overhead. The bottom-up tables above fill every cell in a fixed order and avoid recursion.

Both approaches compute the same recurrence: dp[r][c] depends on the cells it points to.

Java
1static long[][] memo;
2static long paths(int r, int c, int[][] g) {                   // paths from (r, c) to the bottom-right, moving down or right
3    if (r >= g.length || c >= g[0].length || g[r][c] == 1) return 0;
4    if (r == g.length - 1 && c == g[0].length - 1) return 1;
5    if (memo[r][c] != -1) return memo[r][c];
6    return memo[r][c] = paths(r + 1, c, g) + paths(r, c + 1, g);
7}
8// setup: memo = new long[R][C]; for (long[] row : memo) Arrays.fill(row, -1);

Practice ladder

Now try it yourself

Easy

  • Fill the minimum path sum table for [[1, 2], [3, 4]]
  • How many unique paths exist in a 3 × 3 grid?

Medium

  • Count unique paths in a grid with one obstacle in the centre
  • Find the maximal square in a 4 × 4 binary matrix

Advanced

  • Reduce the minimum path sum to O(C) extra space and also reconstruct one optimal path

Key takeaways

  • Define dp[r][c] clearly, then write the recurrence from the cells above and to the left.
  • Obstacles force 0 paths; squares use 1 + min of three neighbours.
  • Memoised recursion and bottom-up tables compute the same values.