Grid DP

At a glance

The instinct

A grid problem becomes DP when movement cannot loop back: only right and down, only to the next row, or only toward strictly larger values. Then every cell has a fixed set of "parents" (cells that can step into it) and you can define dp[r][c] = the answer for reaching (or starting from) that cell. Fill the table in an order where parents are always ready - usually row by row, left to right.

If movement is free in all four directions with costs, that is a shortest-path problem, not grid DP. The no-cycles rule is what makes a table possible.

Recognise it

Not this pattern if...

• Moves go in all directions with non-negative costs: use Dijkstra or BFS.
• You only need connected regions or reachability: DFS/BFS flood fill.
• The two indices are positions in two strings: same table shape, but think String DP.

Memory hack

DP framing: state dp[r][c] = best result for reaching (r, c); choice = which parent you came from; base case = start cell plus the first row/column, or blocked cells as 0 / infinity; order = top-to-bottom, left-to-right (or reversed for bottom-up problems like Triangle).

Analogy: water poured at the top-left corner of a sloped tray. It can only run down and right, so each cell's water is whatever flows in from above and from the left. You can compute every cell once, in the direction the water flows.

Say it out loud in the interview:

1. "Movement only goes right/down, so the dependency graph has no cycles."
2. "dp[r][c] = cell value combined with the best of its parents."
3. "Each row only reads the previous row, so one 1-D array of width cols is enough."

How it works

Pick the state, identify the parents, seed the edges, and sweep. For Minimum Path Sum on

1 3 1
1 5 1
4 2 1

the filled table is:

Since row r only reads row r - 1 and the cell to its left, a single array dp[c] works: before the update, dp[c] still holds the value from above; dp[c-1] already holds the new value on the left.

When the dependency order is awkward (any-direction moves with a strictly increasing rule), skip the ordering puzzle: write a DFS that returns the answer for a cell and memoise it. The recursion discovers the right order automatically.

Java template

import java.util.*;

class GridDP {
    // Bottom-up, one rolling row. Example: min-cost path moving right/down; -1 marks a blocked cell.
    static int minPathCost(int[][] g) {
        int rows = g.length, cols = g[0].length;
        final int INF = Integer.MAX_VALUE / 2;
        int[] dp = new int[cols];
        Arrays.fill(dp, INF);
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (g[r][c] == -1) { dp[c] = INF; continue; }      // obstacle
                if (r == 0 && c == 0) { dp[c] = g[r][c]; continue; } // start cell
                int fromTop = dp[c];                                // previous row, same column
                int fromLeft = c > 0 ? dp[c - 1] : INF;             // current row, already updated
                int best = Math.min(fromTop, fromLeft);             // swap for +, max, etc.
                dp[c] = best >= INF ? INF : best + g[r][c];
            }
        }
        return dp[cols - 1] >= INF ? -1 : dp[cols - 1];
    }

    // Top-down memo for grids without an obvious fill order (dependency must still be acyclic).
    static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    static int longestIncreasingPath(int[][] g) {
        int[][] memo = new int[g.length][g[0].length];
        int best = 0;
        for (int r = 0; r < g.length; r++)
            for (int c = 0; c < g[0].length; c++)
                best = Math.max(best, dfs(g, r, c, memo));
        return best;
    }

    static int dfs(int[][] g, int r, int c, int[][] memo) {
        if (memo[r][c] != 0) return memo[r][c];
        int best = 1;                                               // the cell alone
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nc < 0 || nr >= g.length || nc >= g[0].length) continue;
            if (g[nr][nc] <= g[r][c]) continue;                     // rule that prevents cycles
            best = Math.max(best, 1 + dfs(g, nr, nc, memo));
        }
        return memo[r][c] = best;
    }
}

Complexity

• Time: O(R × C × p), where p is the number of parents per cell - usually a constant, so O(R × C).
• Space: O(R × C) for a full table or memo; O(C) with a rolling row; O(1) extra if you may overwrite the input.
• Bigger states cost more: Cherry Pickup is O(n³) with state (step, r1, r2); interval DP like Burst Balloons is O(n³).

Variations

• Count paths: Unique Paths / Unique Paths II - dp[c] += dp[c-1], obstacles reset to 0.
• Min/max cost path: Minimum Path Sum - grid + min(top, left).
• Bottom-up triangle: Triangle - start from the last row, dp[c] = val + min(dp[c], dp[c+1]); the answer ends in dp[0], with no edge cases.
• Square-ending-here: Count Square Submatrices with All Ones and Maximal Square - 1 + min(top, left, topLeft); summing dp counts squares, the max gives the largest.
• Row-to-row with distance penalty: Maximum Number of Points with Cost - two sweeps per row (left-to-right and right-to-left running max) cut O(C²) to O(C).
• Memoised DFS on a DAG grid: Longest Increasing Path in a Matrix - strict increase guarantees no cycles.
• Two walkers: Cherry Pickup - move both at once so they share the step count; count a shared cell once.
• Interval table: Burst Balloons - dp[i][j] over a range, choosing the last balloon k to burst; fill by increasing length.
• Sorted-items table: Maximum Profit in Job Scheduling - sort by end time, dp[i] = max(skip, profit + dp[last compatible job]) with binary search.

Common mistakes

• Wrong fill order. Reading a cell before it is computed gives garbage; trace one cell's parents before writing loops.
• Overflow in min problems. Using Integer.MAX_VALUE and then adding the cell value wraps negative; use MAX_VALUE / 2 or check first.
• Top-down Triangle edge cases. Going top-down needs special handling for both edges; bottom-up avoids it entirely.
• Applying grid DP to 4-direction movement. Cycles make the recurrence circular; use shortest path unless a strict rule (like increasing values) removes cycles.
• Double-counting in Cherry Pickup when both walkers land on the same cell.

All practice problems

10 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.