templates · Dynamic programming

Grid DP

  • A grid where you may only move right or down (or one row to the next)
  • "Count the paths", "cheapest path" or "largest square" in a matrix
  • Each cell's answer comes from its top, left or top-left neighbour

Grid DP

the one rule

The invariant

When you fill dp[r][c], the cells above it and to its left are already final.

write it from memory

The template

count paths (with blocked cells)

javajava.util.*
/** Unique Paths II: count right/down paths from top-left to bottom-right; 1 = blocked cell. */static int countPaths(int[][] grid) {    int rows = grid.length;    if (rows == 0 || grid[0].length == 0) return 0;    int cols = grid[0].length;    long[][] dp = new long[rows][cols];                  // dp[r][c] = paths that reach cell (r, c)    for (int r = 0; r < rows; r++) {        for (int c = 0; c < cols; c++) {            if (grid[r][c] == 1) continue;               // blocked: zero ways in            if (r == 0 && c == 0) {                dp[r][c] = 1;                            // base case: the start                continue;            }            long fromTop = r > 0 ? dp[r - 1][c] : 0;            long fromLeft = c > 0 ? dp[r][c - 1] : 0;            dp[r][c] = fromTop + fromLeft;               // you arrive from above or from the left        }    }    return (int) dp[rows - 1][cols - 1];}

Counting uses +. A blocked cell stays 0, so no path passes through it. Like an Excel sheet where each cell adds the one above and the one on the left.

fill in the blanks — only these lines change per problem

  1. line 6What a cell stores: number of paths, cheapest cost, or the side of the biggest square ending here.
  2. line 9Cells that no path may use. Leave them at the neutral value (0 for counting, "infinity" for min).
  3. line 11The start cell's value: 1 way, or its own cost.
  4. line 16How the neighbours combine: top + left, min(top, left) + cost, or min(top, left, diag) + 1 for squares.

cheapest path

javajava.util.*
/** Minimum Path Sum: cheapest right/down path, the cost of a path is the sum of its cells. */static int minPathSum(int[][] grid) {    int rows = grid.length, cols = grid[0].length;    int[][] dp = new int[rows][cols];                    // dp[r][c] = cheapest cost to stand on (r, c)    for (int r = 0; r < rows; r++) {        for (int c = 0; c < cols; c++) {            if (r == 0 && c == 0) dp[r][c] = grid[0][0]; // base case            else if (r == 0) dp[r][c] = dp[r][c - 1] + grid[r][c];   // first row: only from the left            else if (c == 0) dp[r][c] = dp[r - 1][c] + grid[r][c];   // first column: only from above            else dp[r][c] = Math.min(dp[r - 1][c], dp[r][c - 1]) + grid[r][c];        }    }    return dp[rows - 1][cols - 1];}

Best-cost uses min. The first row and first column have only one way in, so handle them as their own case.

fill in the blanks — only these lines change per problem

  1. line 8The first row (and column) only has one neighbour; handle it before the general rule.

complexity

What it costs

time O(rows × cols)
Each cell is filled once with O(1) work from its neighbours.
space O(rows × cols), or O(cols)
One value per cell. Since a row only reads the row above, one row of dp is enough if you need to save memory.

watch out

Common bugs

  • Reading dp[r - 1][c] on the first row: guard it, or add a padding row of zeros.
  • Forgetting that the start or the end cell itself can be blocked.
  • Adding path counts in int when they can be large. This code adds in long and casts only at the end, because LeetCode promises the final answer fits in an int.

use it

Practise it on

learn it properly