Grid DP: forward fills, backward survives

m = 3, n = 7. A robot at (0, 0) walks down or right, one cell at a time, to (2, 6). How many distinct routes? The answer is 28, and a freshly-graduated computer-science major can produce it three ways: by enumerating paths and timing out, by writing a recursion that takes longer than the heat death of the universe at m = n = 100, or by filling a 3 x 7 table top-to-bottom with one addition per cell. The third way is the chapter. So is the question that breaks it.

The breaking question is Dungeon Game, LC 174. Same m x n grid. The robot is now a knight; cells contain HP deltas instead of being unweighted; the knight starts at (0, 0) with some unknown HP H and must reach (m-1, n-1) with HP staying at least 1 at every cell. Find the minimum H.^[1] The recurrence that worked on Unique Paths refuses to work here, and the reason is the chapter's central idea: in grid DP, the iteration order is not a stylistic choice. It follows the dependency direction, and the dependency direction follows the question.

Locating this pattern#

The diagnostic question for any 2D-grid problem is: given a destination cell (i, j), which cells could have been the LAST step before arriving here? If the answer is a small finite set of predecessors whose own DP values are already computed under some natural fill order, you have a grid DP. The recurrence has a fixed shape: dp[i][j] = combine(dp[predecessor_1], dp[predecessor_2], ..., cell_cost[i][j]). The combine operator changes; the shape does not.

The combine operator is the discriminator. Counting uses +. Optimizing uses min(...) + cost or its max twin. When the predicate at the destination depends on what comes after each cell, iteration reverses and the operator becomes max(min(...) - cost, 1).

Why brute force burns#

The signature problem is LC 62, Unique Paths.^[2] An m x n grid; a robot at the top-left moves only right or down to reach the bottom-right; return the count of distinct paths. The honest first attempt enumerates them by recursion.

# Brute force: O(2^(m+n)) — what we're replacing
def unique_paths_brute(m, n):
    def paths_from(i, j):
        if i == m - 1 and j == n - 1:
            return 1
        total = 0
        if i + 1 < m:
            total += paths_from(i + 1, j)
        if j + 1 < n:
            total += paths_from(i, j + 1)
        return total
    return paths_from(0, 0)

Correct on m = n = 3. Catastrophic past about m = n = 14. Every distinct path is its own leaf in the recursion tree, so the call count grows with the number of paths, which is the answer the algorithm is trying to compute. At LC 62's stated bound m, n <= 100 the call tree has roughly C(198, 99) leaves, a number with 58 digits, and there is not enough silicon on Earth to evaluate it.^[2:1]

The waste is also obvious by inspection. paths_from(2, 3) is computed by every distinct path that arrives at (2, 3), and there are many. The function call has no memory; it re-derives the same answer over and over. Memoize it and the count of distinct subproblems collapses to m * n, one per cell. That is the grid DP.

The pattern#

Define dp[i][j] as the number of distinct right-or-down paths from (0, 0) to (i, j). The last step into (i, j) came from (i-1, j) (above) or from (i, j-1) (left). Total paths to (i, j) is the sum of paths to those two predecessors. Base cases dp[0][j] = dp[i][0] = 1 because the top row and left column each have exactly one monotone path.^[2:2]

Each cell reads its top neighbor and left neighbor, then is itself read by its bottom and right successors. Row-major top-to-bottom, left-to-right fill keeps every read on a value already written.

# LC 62. Unique Paths
"""Forward grid DP: count monotone right/down paths from (0, 0) to (m-1, n-1).

The recurrence is the unweighted count `dp[i][j] = dp[i-1][j] + dp[i][j-1]`,
filled row-major top-to-bottom, left-to-right. Two implementations: the
full 2D table for clarity, and the rolling 1D row for `O(min(m, n))` space.
"""

from typing import List


def unique_paths_2d(m: int, n: int) -> int:
    """Full 2D table DP. dp[i][j] = dp[i-1][j] + dp[i][j-1]."""
    dp = [[0] * n for _ in range(m)]
    for j in range(n):
        dp[0][j] = 1
    for i in range(m):
        dp[i][0] = 1
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]


def unique_paths_1d(m: int, n: int) -> int:
    """Rolling 1D row. O(m*n) time, O(min(m, n)) space."""
    if m < n:
        m, n = n, m
    dp = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            dp[j] = dp[j] + dp[j - 1]
    return dp[n - 1]


def unique_paths(m: int, n: int) -> int:
    """LeetCode-shaped entry point. Defaults to the full 2D table."""
    return unique_paths_2d(m, n)

// LC 62. Unique Paths
public final class Sol {

    /** Full 2D table DP. dp[i][j] = dp[i-1][j] + dp[i][j-1]. */
    public static int uniquePaths2d(int m, int n) {
        int[][] dp = new int[m][n];
        for (int j = 0; j < n; j++) dp[0][j] = 1;
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    /** Rolling 1D row. dp[j] += dp[j-1] in place. */
    public static int uniquePaths1d(int m, int n) {
        if (m < n) { int t = m; m = n; n = t; }
        int[] dp = new int[n];
        for (int j = 0; j < n; j++) dp[j] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] = dp[j] + dp[j - 1];
            }
        }
        return dp[n - 1];
    }

    /** LeetCode-shaped public entry point. */
    public int uniquePaths(int m, int n) {
        return uniquePaths2d(m, n);
    }
}

// LC 62. Unique Paths
#include <vector>
#include <algorithm>

class Solution {
public:
    /** Full 2D table DP. dp[i][j] = dp[i-1][j] + dp[i][j-1]. */
    static int uniquePaths2d(int m, int n) {
        std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));
        for (int j = 0; j < n; ++j) dp[0][j] = 1;
        for (int i = 0; i < m; ++i) dp[i][0] = 1;
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    /** Rolling 1D row. dp[j] += dp[j-1] in place. */
    static int uniquePaths1d(int m, int n) {
        if (m < n) std::swap(m, n);
        std::vector<int> dp(n, 1);
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[j] = dp[j] + dp[j - 1];
            }
        }
        return dp[n - 1];
    }

    /** LeetCode-shaped public entry point. */
    int uniquePaths(int m, int n) {
        return uniquePaths2d(m, n);
    }
};

// LC 62. Unique Paths
package main

// UniquePaths2d fills the full m x n table.
func UniquePaths2d(m, n int) int {
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	for j := 0; j < n; j++ {
		dp[0][j] = 1
	}
	for i := 0; i < m; i++ {
		dp[i][0] = 1
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	return dp[m-1][n-1]
}

// UniquePaths1d uses a rolling row for O(min(m, n)) space.
func UniquePaths1d(m, n int) int {
	if m < n {
		m, n = n, m
	}
	dp := make([]int, n)
	for j := 0; j < n; j++ {
		dp[j] = 1
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[j] = dp[j] + dp[j-1]
		}
	}
	return dp[n-1]
}

// uniquePaths is the LeetCode-shaped public entry point.
func uniquePaths(m, n int) int {
	return UniquePaths2d(m, n)
}

The fill order is the line worth pausing on. dp[i][j] reads two cells: the one above and the one to the left. Iterating i from 0 upward and j from 0 upward guarantees both reads land on already-written values. Reverse either loop and the recurrence reads zeros. This is not a quirk; every grid DP shares the rule, and getting it wrong is the source of half the bugs in the family. State the dependency above the loop in plain English. If you cannot say which two cells the recurrence reads, the loop bounds are guessing.^[2:3]

The space cost can drop. dp[i][*] depends only on dp[i-1][*] plus the just-written entries of the current row, so a single row buffer plus in-place updates suffice: dp[j] = dp[j] + dp[j-1] is exactly dp_new[j] = dp_old[j] + dp_new[j-1] because at the moment we evaluate the right-hand side, dp[j] is still the old-row value (we have not overwritten it yet) and dp[j-1] is already the new-row value (we just wrote it last iteration). Total space drops from O(m*n) to O(min(m, n)). Same recurrence, one fewer dimension.^[2:4]

The recurrence as a family#

Every monotone-direction grid recurrence has the same shape. Only the combine operator and the base cases change.

LC 62 to LC 64 is one operator swap: + becomes min(...) + cell. LC 63 adds an obstacle short-circuit and the equivalent rule on the base row (a single blocked cell at column c in row 0 makes every later cell in row 0 unreachable, so the loop must break, not continue).^[3] LC 931 generalizes "the start is the corner" to "the start is anywhere in row 0", which gives every cell of row 0 a base-case value and asks the answer over the entire bottom row. The recurrence reads three predecessors instead of two because the path can step diagonally.

The fifth row is what breaks the family. Look at it.

The twist: when forward DP refuses to work#

LC 174 Dungeon Game reads almost identically to LC 64. A m x n grid. Cells contain integers, possibly negative. Find the optimal sum along a right-or-down path from corner to corner. The difference fits in one sentence: in LC 64 the answer IS the optimal sum; in LC 174 the answer is the minimum starting HP such that the cumulative HP stays at least 1 at every cell, including the destination.^[1:1] One sentence longer in the problem statement; an order-of-magnitude shift in the DP.

Try forward DP first. Define dp[i][j] as the minimum HP required to walk from (0, 0) to (i, j). The last step came from above or from the left. Recurrence:

# WRONG: forward DP for LC 174 — does not work
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + ???

There is no clean ??? because the HP requirement at (i, j) is not a function of "HP required up to the predecessor" alone. It depends on what HP the knight had on arrival, which depends on the entire path so far, which is more than dp[i-1][j] knows. To capture it forward, the state needs two dimensions, minimum HP needed so far AND current HP, and the cell count explodes from m * n to something exponential in the cell-value range. The forward formulation is not slow; it is not memoizable.^[4]

The reframe is one sentence. Iterate from the destination back to the source. Define dp[i][j] as the minimum HP required ON ENTERING (i, j) to survive from (i, j) onward. The two successors are (i+1, j) (below) and (i, j+1) (right). Whichever successor needs less HP on entry is the one the knight should walk into; given that, the knight needs enough HP at (i, j) to cover the cell's own delta and still meet the successor's threshold:

dp[i][j] = max(min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j], 1)

The outer max(..., 1) clamp is the survival predicate enforced cell by cell: the knight cannot enter any cell with less than 1 HP, even if a giant power-up at the cell would otherwise make the math suggest 0 or negative. Sentinel base cells dp[m][n-1] = dp[m-1][n] = 1 mean the knight needs at least 1 HP to be alive after the destination cell resolves.^[4:1]

LC 64 fills top-left to bottom-right because each cell depends on its top and left predecessors. LC 174 fills bottom-right to top-left because the survival predicate depends on successors. The arrows are the dependency direction; the iteration order is the arrows reversed.

# LC 174. Dungeon Game
# Recurrence:
#   dp[i][j] = max(min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j], 1)
# Sentinel base cells dp[m][n-1] = dp[m-1][n] = 1 enforce "knight must
# arrive with at least 1 HP". Iteration is bottom-right to top-left.
"""Backward grid DP: minimum starting HP for a knight to reach the princess.

Forward DP fails because the survival predicate "HP >= 1 at every cell"
depends on the suffix of the path, not the prefix. Iterating from
(m-1, n-1) back to (0, 0) lets each cell read its already-computed
successors and take the cheaper one.
"""

from typing import List


def calculate_minimum_hp(dungeon: List[List[int]]) -> int:
    m = len(dungeon)
    n = len(dungeon[0])
    # dp[i][j] = minimum HP required ON ENTERING (i, j) to survive the path.
    # Pad with sentinel inf so the (m-1, n-1) cell reads min(inf, inf) and
    # falls back to its own clamp.
    INF = float("inf")
    dp = [[INF] * (n + 1) for _ in range(m + 1)]
    dp[m][n - 1] = 1
    dp[m - 1][n] = 1
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
            dp[i][j] = max(need, 1)
    return dp[0][0]

// LC 174. Dungeon Game
// Backward grid DP:
//   dp[i][j] = max(min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j], 1)
// Sentinel padding with Integer.MAX_VALUE so the bottom-right corner falls
// back to its own clamp; iteration is bottom-right to top-left.
public final class Sol {

    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        dp[m][n - 1] = 1;
        dp[m - 1][n] = 1;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int need = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = Math.max(need, 1);
            }
        }
        return dp[0][0];
    }
}

// LC 174. Dungeon Game
// Backward grid DP:
//   dp[i][j] = max(min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j], 1)
// Sentinel padding with INT_MAX so the bottom-right corner falls back to
// its own clamp; iteration is bottom-right to top-left.
#include <vector>
#include <algorithm>
#include <climits>

class Solution {
public:
    int calculateMinimumHP(std::vector<std::vector<int>>& dungeon) {
        int m = (int)dungeon.size();
        int n = (int)dungeon[0].size();
        std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, INT_MAX));
        dp[m][n - 1] = 1;
        dp[m - 1][n] = 1;
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                int need = std::min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = std::max(need, 1);
            }
        }
        return dp[0][0];
    }
};

// LC 174. Dungeon Game
// Backward grid DP:
//   dp[i][j] = max(min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j], 1)
// Sentinel padding with math.MaxInt32 so the bottom-right corner falls
// back to its own clamp; iteration is bottom-right to top-left.
package main

import "math"

func calculateMinimumHP(dungeon [][]int) int {
	m := len(dungeon)
	n := len(dungeon[0])
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
		for j := range dp[i] {
			dp[i][j] = math.MaxInt32
		}
	}
	dp[m][n-1] = 1
	dp[m-1][n] = 1
	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			need := min2(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]
			dp[i][j] = max2(need, 1)
		}
	}
	return dp[0][0]
}

func min2(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max2(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Worked example: LC 62 on m = 3, n = 7#

The 3-by-7 table fills row by row. The top row and left column seed to 1. Each interior cell is the sum of the cell above and the cell to its left.

Row 1 is the running prefix sum of row 0. Row 2 is the running prefix sum of row 1. The bottom-right cell is 28, which is also the central binomial coefficient C(m + n - 2, m - 1) = C(8, 2) = 28, the closed form for the count of monotone lattice paths between two corners. Both routes confirm the answer.^[5]

The closed form runs in O(min(m, n)) time and O(1) space, and it is mathematically delightful, but it does not generalize. Add an obstacle (LC 63), add cell weights (LC 64), reverse the dependency (LC 174), and the binomial identity disappears. The DP is the technique that survives every variant.

What it actually costs#

The O(m*n) time is the minimum possible for any algorithm that must read every cell, since Omega(m*n) is the lower bound on reading the input. O(m*n) is achievable because every cell is written exactly once and read by at most a constant number of successors; total work per cell is O(1). Space drops to O(min(m, n)) whenever the recurrence has a one-step dependency, which is true for every member of the family.^[6:1]

LC 62's stated constraint 1 <= m, n <= 100 plus the guarantee "the answer is at most 2 * 10^9" means a 32-bit signed integer holds the count (INT_MAX is 2_147_483_647). The chapter's reference implementations use int accordingly. Generalize the same recurrence to grids with n = 1000 and the count overflows around n = 16; promote to long / int64 or use the closed form computed with arbitrary-precision arithmetic.^[8]

When the pattern bends#

The four variants below cover almost everything in interview rotation. Each is a one-line edit on the canonical recurrence.

Obstacles: short-circuit the recurrence and the base loop#

LC 63 Unique Paths II adds blocked cells. The interior recurrence becomes dp[i][j] = 0 if obstacle[i][j] else dp[i-1][j] + dp[i][j-1]. The subtle bug lives in the base row and base column. A blocked cell at (0, c) in the top row makes every cell to its right unreachable along a top-row path; the base loop must break at the first obstacle, not continue. Copy the LC 62 base loop verbatim and you set dp[0][c+k] = 1 for every later cell, fictitiously letting paths leak past the wall.^[3:2]

Mixed move set: the falling-path recurrence reads three predecessors#

LC 931 Min Falling Path Sum generalizes "start at a corner" to "start at any cell of row 0", and lets each step go down-left, straight down, or down-right. The recurrence reads three predecessors: dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + matrix[i][j], with bounds checks on j-1 and j+1. The base row is dp[0][j] = matrix[0][j] for all j, and the answer is the minimum over the entire bottom row. The triangle problem LC 120 has the same shape on a triangular grid, and trips readers who pad it to a square and then read fictitious zeros from the phantom cells.^[9]

Strict-increase predicate: the implicit DAG and DFS-with-memo#

LC 329 Longest Increasing Path in a Matrix is the variant where the move set becomes 4-directional but a strict-increase predicate matrix[next] > matrix[cur] makes the cell-graph acyclic anyway. Define dp[i][j] as the longest strictly-increasing path starting at (i, j). Compute it by DFS-with-memoization: each cell is computed once after its larger-valued neighbors have been computed, and the topological order is implicit in the recursion. Total work O(m*n). The naive DFS without memoization is O(2^(m*n)) and times out on LC's 200-by-200 hidden tests.^[7:1]

LC 329 builds an implicit DAG over grid cells where edges go from smaller-valued cells to strictly-larger 4-neighbors. DFS+memo on this DAG computes dp[i][j] in O(m*n) total because each cell is computed exactly once and each edge is traversed at most twice.

Closed form: Pascal's triangle in disguise#

The LC 62 path count is exactly the number of distinct binary strings of length m + n - 2 containing m - 1 "down" moves and n - 1 "right" moves, which is C(m + n - 2, m - 1). Computed as a running product of min(m - 1, n - 1) terms, the closed form runs in O(min(m, n)) time and O(1) space. It is faster than the DP and asymptotically beats it whenever the closed form applies. It does not apply to LC 63 (obstacles), LC 64 (weighted cells), or LC 174 (backward survival).^[5:2]

Three pitfalls that bite#

Problem ladder#

The grid-DP pattern is structurally Medium- and Hard-bound. Every monotone-direction recurrence on a 2D grid lands at LC Medium because the 2D state and base-case bookkeeping push it past the Easy bar; the Hard variants (LC 174, LC 329) layer either backward iteration or a graph-DP cross-over on top. The 1D DP precursors that LC ranks Easy, namely LC 70 Climbing Stairs and LC 198 House Robber, live in DP 1D, where their mechanics are introduced from scratch. Pulling them into this chapter would distort both pages.

CORE (solve all three to claim chapter mastery)#

• LC 62 — Unique Paths [Medium] • grid-dp-path-count ★
• LC 64 — Minimum Path Sum [Medium] • grid-dp-min-path
• LC 174 — Dungeon Game [Hard] • grid-dp-backward

STRETCH (optional)#

• LC 329 — Longest Increasing Path in a Matrix [Hard] • grid-dp-on-dag-memo
• LC 931 — Minimum Falling Path Sum [Medium] • grid-dp-multi-source

LC 62 is the chapter's signature problem and the cleanest introduction. The CORE three exercise the three load-bearing variations on the recurrence: counting (LC 62), forward optimization (LC 64), and backward survival (LC 174). The two stretch problems extend the family in different directions: LC 329 with the implicit-DAG framing, LC 931 with the multi-source generalization. LC 63 (Unique Paths II) and LC 120 (Triangle) are covered in the chapter prose as one-line variations on LC 62 and LC 64 respectively; both are worth solving but neither earns a ladder slot under the five-entry cap.

Where this leads#

Tree DP is the next chapter, and the recurrence shape inverts: instead of cell-from-predecessors, it is parent-from-children. The structural similarity is "DP on a graph", with trees the easiest DAG to recurse on and grids the second-easiest. Readers who saw the dependency-direction frame in this chapter will recognize the same machinery on first read of the tree-DP problems.

Two prior chapters quietly became the foundation for everything here. DP bottom-up tabulation introduced the iterate-by-fill-order technique; this chapter is its canonical 2D application. DP 1D taught dp[i] = combine(dp[i-1], ...) on a 1D state, with LC 70 and LC 198 as the precursors a reader should solve before LC 62. The 1D-to-2D step is small in code and large in conceptual surface: the dependency direction stops being trivially obvious, the base cases double from one to two, and the iteration order becomes a thing you have to think about.

When the move set relaxes from "right and down only" to four-directional or eight-directional with no monotone score predicate, the cell-graph stops being a DAG and grid DP no longer applies. Those problems live in Part 8: Grid traversal with BFS handles shortest-step questions, and depth-first search handles connected components. The trigger for choosing this chapter over those is the move set: monotone direction OR a strict-increase predicate makes the graph acyclic, which makes DP work; arbitrary 4-directional movement does not.

References#