Dynamic Programming on Grids: Unique Paths, Minimum Path Sum, and Dungeon Game (2025)

Grid DP Fundamentals

Grid DP problems define a 2D state space where dp[i][j] represents some optimum property at cell (i, j). The recurrence uses adjacent cells (typically from the top and left for top-down traversal). Grid DP is a subtype of 2D DP — most grid problems reduce to: dp[i][j] = f(dp[i-1][j], dp[i][j-1], grid[i][j]). Recognizing the recurrence direction (top-left to bottom-right, or in reverse for path problems starting from the bottom-right) is the key first step.

Pattern 1: Unique Paths (LC 62, 63)

Count paths from (0,0) to (m-1, n-1) moving only right or down. dp[i][j] = number of ways to reach (i, j) = dp[i-1][j] + dp[i][j-1]. Base: dp[0][j] = 1 (only one way to reach any cell in the first row: keep going right). dp[i][0] = 1 (keep going down). With obstacles (LC 63): dp[i][j] = 0 if obstacle, else dp[i-1][j] + dp[i][j-1]. Space optimization: only need the current and previous row → O(n) space.

def unique_paths_with_obstacles(grid):
    m, n = len(grid), len(grid[0])
    dp = [0] * n
    dp[0] = 1  # start if not blocked
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                dp[j] = 0  # obstacle
            elif j > 0:
                dp[j] += dp[j-1]
    return dp[n-1]

Pattern 2: Minimum Path Sum (LC 64)

Find the path from (0,0) to (m-1, n-1) with minimum total cost. dp[i][j] = min cost to reach (i, j). dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). In-place: modify grid directly (avoids extra space). Handle edges: first row has only one path (keep going right), first column only one path (keep going down).

def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0: continue
            top  = grid[i-1][j] if i > 0 else float('inf')
            left = grid[i][j-1] if j > 0 else float('inf')
            grid[i][j] += min(top, left)
    return grid[m-1][n-1]

Pattern 3: Dungeon Game (LC 174)

A knight starts at (0,0), must reach (m-1, n-1). Each cell has a value (positive = health gained, negative = health lost). Knight dies if health drops to 0 or below at any point. Find the minimum initial health. Key insight: cannot solve left-to-right (greedy path maximizing health fails). Must solve right-to-left: dp[i][j] = minimum health needed when entering cell (i, j) to survive the rest of the dungeon.

def calculate_minimum_hp(dungeon):
    m, n = len(dungeon), len(dungeon[0])
    dp = [[float('inf')] * (n+1) for _ in range(m+1)]
    dp[m][n-1] = dp[m-1][n] = 1  # sentinel: 1 health to enter the exit cell

    for i in range(m-1, -1, -1):
        for j in range(n-1, -1, -1):
            min_health_after = min(dp[i+1][j], dp[i][j+1])
            dp[i][j] = max(1, min_health_after - dungeon[i][j])
    return dp[0][0]

The formula max(1, next_needed – cell_value): if the cell has positive value, it reduces the health needed; if negative, increases it. Must be at least 1 (can’t start with 0 or negative health). This reverse-DP pattern appears whenever the constraint is about surviving a future state.

Pattern 4: Maximal Square and Triangle

Maximal Square (LC 221): find the largest square of 1s in a binary matrix. dp[i][j] = side length of the largest square with bottom-right corner at (i, j). If grid[i][j] == 1: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. If == 0: dp[i][j] = 0. The minimum of the three neighbors is the bottleneck — the square can only be as large as the smallest of the squares extending from the top, left, and top-left neighbors. Track the global maximum. O(mn) time and O(n) space (one row at a time). Cherry Pickup (LC 741): two passes on a grid (there and back). Key insight: model as two simultaneous walkers both starting at (0,0) and ending at (n-1, n-1). dp[t][r1][r2] where t = step count (r1 + c1 = r2 + c2 = t). O(n^3) states instead of O(n^4).

{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the general recurrence for grid DP problems moving from top-left to bottom-right?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”For most grid DP problems where you can only move right or down: dp[i][j] = f(dp[i-1][j], dp[i][j-1], grid[i][j]). The exact function f depends on the problem: for unique paths it's addition, for minimum path sum it's min + grid value, for obstacle problems it's 0 if blocked. Base cases: dp[0][j] = g(dp[0][j-1]) and dp[i][0] = g(dp[i-1][0]) (only one way to reach any cell in the first row or column).”}},{“@type”:”Question”,”name”:”Why does the Dungeon Game require right-to-left DP rather than left-to-right?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”In the Dungeon Game, you need the knight to survive with minimum initial health. A greedy left-to-right approach fails because a path with high health at the start might route through lethal cells later. Right-to-left DP defines dp[i][j] as the minimum health needed entering (i,j) to survive the rest of the dungeon. At the exit cell, you need at least 1 health. Working backwards, dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) – dungeon[i][j]) — the minimum health to survive from here.”}},{“@type”:”Question”,”name”:”How do you space-optimize grid DP from O(mn) to O(n)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Most grid DP only looks at the current row and the previous row (dp[i][j] depends on dp[i-1][j] and dp[i][j-1]). Store a single 1D array of size n. Process left to right: dp[j] holds dp[i-1][j] at the start of iteration j, and dp[j-1] holds dp[i][j-1] (just computed). After updating, dp[j] becomes dp[i][j]. This technique works for unique paths, minimum path sum, and unique paths with obstacles.”}},{“@type”:”Question”,”name”:”What is the recurrence for the Maximal Square problem (LC 221)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”dp[i][j] = side length of the largest square of 1s with bottom-right corner at (i, j). If grid[i][j] == 0: dp[i][j] = 0. Else: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. The minimum of the three neighbors represents the constraint: the square can only be as large as the smallest square that fits at the top, left, and top-left. The answer is max(dp[i][j])^2 (area of the largest square found).”}},{“@type”:”Question”,”name”:”How do you model the Cherry Pickup problem as a grid DP efficiently?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Instead of simulating "there and back," model as two robots starting at (0,0) simultaneously and both reaching (n-1, n-1) in the same number of steps. State: dp[t][r1][r2] where t is the step count and r1, r2 are the row positions of the two robots (columns are derived: c = t – r). If r1 == r2, only count cherries once. This reduces from O(n^4) states to O(n^3) by observing that both robots are always at the same step t.”}}]}