Grid-Based Dynamic Programming: Paths, Costs & Obstacles

1. Introduction & Motivation

Every dynamic programming solution needs two things: a way to name each subproblem (the state) and a rule for building a subproblem's answer from smaller subproblems already solved (the recurrence). In 1D DP problems such as climbing stairs or house robber, the state is just a position along a sequence, and the hardest part of the design is often deciding what that position even means.

Grid DP starts one step ahead. The problem itself is already a 2D array of rows and columns, so the natural state is simply a cell $(r, c)$ in that grid. Most grid DP recurrences follow the same shape: dp[r][c] depends on neighboring cells that have already been solved, almost always the cell above and the cell to the left, because those are the cells a rightward-or-downward walk can have reached first. The grid gives you the index structure for free; your job is to figure out what to store at each index and how neighboring values combine.

This lesson works through that idea in increasing order of difficulty: counting paths, then paths weighted by cost, then paths blocked by obstacles, and finally problems where a single cell is not enough state and you must track an extra resource or direction alongside the row and column.

2. Prerequisites

This lesson builds directly on two earlier parts of the series and does not re-derive either:

• 2D array traversal: comfort reading and writing a matrix by row and column index, iterating in row-major order, and reasoning about boundary indices. See Part 5: Matrices - Special & Sparse if you need a refresher on basic 2D array mechanics before working through the recurrences below.
• General DP methodology: identifying overlapping subproblems, defining state precisely, deriving a recurrence, and choosing memoization versus tabulation. See Part 14: Dynamic Programming Foundations for that methodology in full; this lesson assumes it and applies it directly to grids.

3. A Concrete Example

4. Path Counting: Unique Paths

The base case is the first row and first column: every cell in either one has exactly one way to be reached, since the walk can only ever move in a single straight line to get there. Once those edges are seeded, the recurrence fills the rest of the table in any order that respects "above and left before here" — ordinary row-major order works.

def unique_paths(rows, cols):
    if rows <= 0 or cols <= 0:
        raise ValueError("grid dimensions must be positive")
    dp = [[1] * cols for _ in range(rows)]
    for r in range(1, rows):
        for c in range(1, cols):
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    return dp[rows - 1][cols - 1]

print("Unique paths (3x4):", unique_paths(3, 4))  # Unique paths (3x4): 10

#include <iostream>
#include <vector>
#include <stdexcept>

long long uniquePaths(int rows, int cols) {
    if (rows <= 0 || cols <= 0) {
        throw std::invalid_argument("grid dimensions must be positive");
    }
    std::vector<std::vector<long long>> dp(rows, std::vector<long long>(cols, 1));
    for (int r = 1; r < rows; ++r) {
        for (int c = 1; c < cols; ++c) {
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
        }
    }
    return dp[rows - 1][cols - 1];
}

int main() {
    std::cout << "Unique paths (3x4): " << uniquePaths(3, 4) << '\n';  // Unique paths (3x4): 10
}

public class UniquePaths {
    static long uniquePaths(int rows, int cols) {
        if (rows <= 0 || cols <= 0) {
            throw new IllegalArgumentException("grid dimensions must be positive");
        }
        long[][] dp = new long[rows][cols];
        for (int c = 0; c < cols; c++) dp[0][c] = 1;
        for (int r = 0; r < rows; r++) dp[r][0] = 1;
        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) {
                dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
            }
        }
        return dp[rows - 1][cols - 1];
    }

    public static void main(String[] args) {
        System.out.println("Unique paths (3x4): " + uniquePaths(3, 4)); // Unique paths (3x4): 10
    }
}

An obstacle-free rectangular grid also has a closed-form answer: reaching a cell $m$ rows down and $n$ columns across always takes exactly $m + n - 2$ moves, of which $m - 1$ must be "down" moves in some order, so the count is the binomial coefficient $\binom{m+n-2}{m-1}$. For the 3×4 trace above, $\binom{3+4-2}{3-1} = \binom{5}{2} = 10$, matching the table. The combinatorial shortcut is faster to compute and needs no table at all, but it only works when every path of the right length is legal. As soon as some cells are blocked, the count is no longer a clean function of grid dimensions, and you need the DP table back.

5. Minimum Cost Path

The state and the direction of dependency are identical to Unique Paths; only the combination rule changes from a sum to a cost-plus-minimum. The first row and first column are again special, but this time they accumulate a running cost rather than a constant count, since there is still only one way to reach them but that one way has a total price.

def min_cost_path(grid):
    if not grid or not grid[0]:
        raise ValueError("grid must be non-empty")
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]
    for c in range(1, cols):
        dp[0][c] = dp[0][c - 1] + grid[0][c]
    for r in range(1, rows):
        dp[r][0] = dp[r - 1][0] + grid[r][0]
    for r in range(1, rows):
        for c in range(1, cols):
            dp[r][c] = grid[r][c] + min(dp[r - 1][c], dp[r][c - 1])
    return dp[rows - 1][cols - 1]

sample = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1],
]
print("Minimum cost path:", min_cost_path(sample))  # Minimum cost path: 7

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>

long long minCostPath(const std::vector<std::vector<int>>& grid) {
    if (grid.empty() || grid[0].empty()) {
        throw std::invalid_argument("grid must be non-empty");
    }
    int rows = grid.size(), cols = grid[0].size();
    std::vector<std::vector<long long>> dp(rows, std::vector<long long>(cols, 0));
    dp[0][0] = grid[0][0];
    for (int c = 1; c < cols; ++c) dp[0][c] = dp[0][c - 1] + grid[0][c];
    for (int r = 1; r < rows; ++r) dp[r][0] = dp[r - 1][0] + grid[r][0];
    for (int r = 1; r < rows; ++r) {
        for (int c = 1; c < cols; ++c) {
            dp[r][c] = grid[r][c] + std::min(dp[r - 1][c], dp[r][c - 1]);
        }
    }
    return dp[rows - 1][cols - 1];
}

int main() {
    std::vector<std::vector<int>> sample{
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1}
    };
    std::cout << "Minimum cost path: " << minCostPath(sample) << '\n';  // Minimum cost path: 7
}

public class MinCostPath {
    static long minCostPath(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            throw new IllegalArgumentException("grid must be non-empty");
        }
        int rows = grid.length, cols = grid[0].length;
        long[][] dp = new long[rows][cols];
        dp[0][0] = grid[0][0];
        for (int c = 1; c < cols; c++) dp[0][c] = dp[0][c - 1] + grid[0][c];
        for (int r = 1; r < rows; r++) dp[r][0] = dp[r - 1][0] + grid[r][0];
        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) {
                dp[r][c] = grid[r][c] + Math.min(dp[r - 1][c], dp[r][c - 1]);
            }
        }
        return dp[rows - 1][cols - 1];
    }

    public static void main(String[] args) {
        int[][] sample = {
            {1, 3, 1},
            {1, 5, 1},
            {4, 2, 1}
        };
        System.out.println("Minimum cost path: " + minCostPath(sample)); // Minimum cost path: 7
    }
}

Obstacles: extending Unique Paths

Now suppose some cells are blocked and contribute zero paths, as if a wall stood there. The recurrence keeps its shape, but a blocked cell always outputs 0 no matter what its neighbors hold, and 0 propagates forward exactly like a broken link: any cell reachable only through a blocked cell inherits that zero.

The subtle part is the first row and first column. Without obstacles they are seeded with a constant 1, but with obstacles a single blocked cell partway along the top row must zero out every cell after it in that row, since the only way to reach those cells was to walk straight through the block. The cleanest way to get this right is to stop treating row 0 and column 0 as a special case at all: initialize a full dp table to zero, set dp[0][0] from whether the start cell itself is blocked, and then let every other cell — including first-row and first-column cells — use the general rule "0 if blocked, otherwise the sum of above and left, where a missing neighbor off the grid counts as 0." A blocked cell early in row 0 then correctly zeroes every cell to its right, because each of those cells has no contribution from above (there is no row −1) and its only remaining source, the cell to the left, is already zero.

def unique_paths_with_obstacles(grid):
    if not grid or not grid[0]:
        raise ValueError("grid must be non-empty")
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = 1 if grid[0][0] == 0 else 0
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                continue
            if grid[r][c] == 1:
                dp[r][c] = 0
                continue
            above = dp[r - 1][c] if r > 0 else 0
            left = dp[r][c - 1] if c > 0 else 0
            dp[r][c] = above + left
    return dp[rows - 1][cols - 1]

sample = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0],
]
print("Paths with obstacle:", unique_paths_with_obstacles(sample))  # Paths with obstacle: 2

#include <iostream>
#include <vector>
#include <stdexcept>

long long uniquePathsWithObstacles(const std::vector<std::vector<int>>& grid) {
    if (grid.empty() || grid[0].empty()) {
        throw std::invalid_argument("grid must be non-empty");
    }
    int rows = grid.size(), cols = grid[0].size();
    std::vector<std::vector<long long>> dp(rows, std::vector<long long>(cols, 0));
    dp[0][0] = (grid[0][0] == 0) ? 1 : 0;
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (r == 0 && c == 0) continue;
            if (grid[r][c] == 1) {
                dp[r][c] = 0;
                continue;
            }
            long long above = (r > 0) ? dp[r - 1][c] : 0;
            long long left = (c > 0) ? dp[r][c - 1] : 0;
            dp[r][c] = above + left;
        }
    }
    return dp[rows - 1][cols - 1];
}

int main() {
    std::vector<std::vector<int>> sample{
        {0, 0, 0},
        {0, 1, 0},
        {0, 0, 0}
    };
    std::cout << "Paths with obstacle: " << uniquePathsWithObstacles(sample) << '\n';  // Paths with obstacle: 2
}

public class UniquePathsWithObstacles {
    static long uniquePathsWithObstacles(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            throw new IllegalArgumentException("grid must be non-empty");
        }
        int rows = grid.length, cols = grid[0].length;
        long[][] dp = new long[rows][cols];
        dp[0][0] = (grid[0][0] == 0) ? 1 : 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (r == 0 && c == 0) continue;
                if (grid[r][c] == 1) {
                    dp[r][c] = 0;
                    continue;
                }
                long above = (r > 0) ? dp[r - 1][c] : 0;
                long left = (c > 0) ? dp[r][c - 1] : 0;
                dp[r][c] = above + left;
            }
        }
        return dp[rows - 1][cols - 1];
    }

    public static void main(String[] args) {
        int[][] sample = {
            {0, 0, 0},
            {0, 1, 0},
            {0, 0, 0}
        };
        System.out.println("Paths with obstacle: " + uniquePathsWithObstacles(sample)); // Paths with obstacle: 2
    }
}

Trace the sample by hand to confirm the first-row/first-column handling: row 0 is [1, 1, 1] since nothing blocks it; column 0 is [1, 1, 1] for the same reason; row 1 becomes [1, 0, 1] because the obstacle at $(1,1)$ zeroes that cell while $(1,2)$ still receives 1 from above; row 2 becomes [1, 1, 2], and the final answer dp[2][2] = 2 matches the two real paths around the block.

6. Multi-State Grid DP

Unique Paths and Minimum Cost Path both get away with a state of just $(r, c)$ because the entire decision at each cell — how many ways, or what cost — can be summarized without remembering anything about the specific path taken to get there. Some grid problems cannot make that simplification. In "Cherry Pickup," two collectors cross the grid at once and the value of a cherry depends on whether both collectors have already visited that cell, so the state must track both collectors' positions together, not just one. In "Dungeon Game," survival at a cell depends on how much health the knight has left, which depends on the specific sequence of damage and healing cells visited so far — a fact that plain $(r, c)$ cannot capture. These problems generalize the grid DP state to $(r, c, \text{extra})$, where extra is whatever additional resource, count, or direction the transition actually depends on.

Dungeon Game is the cleanest worked example of this idea. A knight must walk from the top-left cell of a dungeon to the bottom-right cell, moving only right or down, to rescue a princess. Each cell holds an integer: negative values are damage rooms that subtract from the knight's health, positive values are healing rooms that add to it. The knight's health must stay at 1 or above at every point along the path, including before the very first move. The question is: what is the minimum starting health that guarantees survival all the way to the destination?

Define dp[r][c] as the minimum health the knight must have upon entering cell $(r, c)$ in order to survive from there to the destination. This is where the direction of computation matters. A forward pass, filling dp from the top-left outward, cannot work: the minimum health needed to enter a cell depends on how much danger lies ahead of it, on the unexplored path to the destination, not on how the knight got there. That information only exists once the cells closer to the destination have already been solved. So the table must be filled backward, starting at the destination and working toward the start, exactly the same way the "minimum remaining requirement" framing only makes sense once you know what remains.

Two sentinel rows and columns just past the destination hold "infinity," representing moves that would run off the grid and therefore can never be the cheaper option. The destination cell itself needs at least 1 health after taking its own damage or healing, and every other cell's requirement is: take the smaller of what the cell below and the cell to the right demand, subtract this cell's own effect, and never let the result fall below 1 (a healing room can reduce the requirement, but even a very generous heal never means health could dip to zero or below at any point).

def minimum_health(dungeon):
    if not dungeon or not dungeon[0]:
        raise ValueError("dungeon must be non-empty")
    rows, cols = len(dungeon), len(dungeon[0])
    # dp[r][c] = minimum health needed upon ENTERING cell (r, c).
    # Sentinel row/column hold "infinity" so a move that would run
    # off the grid is never chosen as the minimum.
    inf = float("inf")
    dp = [[inf] * (cols + 1) for _ in range(rows + 1)]
    dp[rows][cols - 1] = 1
    dp[rows - 1][cols] = 1
    for r in range(rows - 1, -1, -1):       # fill backward: destination toward start
        for c in range(cols - 1, -1, -1):
            need = min(dp[r + 1][c], dp[r][c + 1]) - dungeon[r][c]
            dp[r][c] = max(1, need)
    return dp[0][0]

sample = [
    [-2, -3, 3],
    [-5, -10, 1],
    [10, 30, -5],
]
print("Minimum initial health:", minimum_health(sample))  # Minimum initial health: 7

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <stdexcept>

int minimumHealth(const std::vector<std::vector<int>>& dungeon) {
    if (dungeon.empty() || dungeon[0].empty()) {
        throw std::invalid_argument("dungeon must be non-empty");
    }
    int rows = dungeon.size(), cols = dungeon[0].size();
    const long long INF = LLONG_MAX / 2;
    std::vector<std::vector<long long>> dp(rows + 1, std::vector<long long>(cols + 1, INF));
    dp[rows][cols - 1] = 1;
    dp[rows - 1][cols] = 1;
    for (int r = rows - 1; r >= 0; --r) {        // backward: destination toward start
        for (int c = cols - 1; c >= 0; --c) {
            long long need = std::min(dp[r + 1][c], dp[r][c + 1]) - dungeon[r][c];
            dp[r][c] = std::max(1LL, need);
        }
    }
    return static_cast<int>(dp[0][0]);
}

int main() {
    std::vector<std::vector<int>> sample{
        {-2, -3, 3},
        {-5, -10, 1},
        {10, 30, -5}
    };
    std::cout << "Minimum initial health: " << minimumHealth(sample) << '\n';  // Minimum initial health: 7
}

import java.util.Arrays;

public class DungeonGame {
    static int minimumHealth(int[][] dungeon) {
        if (dungeon.length == 0 || dungeon[0].length == 0) {
            throw new IllegalArgumentException("dungeon must be non-empty");
        }
        int rows = dungeon.length, cols = dungeon[0].length;
        long inf = Long.MAX_VALUE / 2;
        long[][] dp = new long[rows + 1][cols + 1];
        for (long[] row : dp) Arrays.fill(row, inf);
        dp[rows][cols - 1] = 1;
        dp[rows - 1][cols] = 1;
        for (int r = rows - 1; r >= 0; r--) {        // backward: destination toward start
            for (int c = cols - 1; c >= 0; c--) {
                long need = Math.min(dp[r + 1][c], dp[r][c + 1]) - dungeon[r][c];
                dp[r][c] = Math.max(1L, need);
            }
        }
        return (int) dp[0][0];
    }

    public static void main(String[] args) {
        int[][] sample = {
            {-2, -3, 3},
            {-5, -10, 1},
            {10, 30, -5}
        };
        System.out.println("Minimum initial health: " + minimumHealth(sample)); // Minimum initial health: 7
    }
}

Trace the last two cells to see the backward logic concretely: dp[2][2] (the destination, damage $-5$) needs max(1, min(1, 1) - (-5)) = 6; dp[2][1] (heal $+30$, to its right sits the already-solved dp[2][2]=6) needs max(1, min(inf, 6) - 30) = 1, because the huge heal covers everything ahead. Continuing this backward sweep to dp[0][0] yields 7, which is the published answer for this classic example. A forward pass could never have produced the "30 covers everything ahead" fact at the moment it examined that cell, because "everything ahead" had not been solved yet — that is precisely why this state must be filled from the goal backward.

7. Complexity Analysis

Every algorithm in this lesson visits each of the $m \times n$ cells a constant number of times and does constant work per cell, so:

The full table is only needed if you must read arbitrary past rows later. In Unique Paths and Minimum Cost Path, row $r$ only ever reads row $r-1$ and its own row-in-progress, so the table can be rolled down to a single 1D array of length $n$, cutting space to $O(n)$:

# Space-optimized Unique Paths: one row, updated in place, left to right.
# row[c] currently holds dp[r-1][c] before the update, dp[r][c] after.
row = [1] * cols
for r in range(1, rows):
    for c in range(1, cols):
        row[c] += row[c - 1]   # row[c] (dp[r-1][c]) + row[c-1] (dp[r][c-1], already updated)
# row[cols - 1] now holds the final answer

The same rolling-array trick applies to Minimum Cost Path by replacing addition with the cost-plus-minimum rule. It does not apply as directly to the obstacle or Dungeon Game variants without care, since both depend on precisely tracking which specific values are "not yet updated" versus "already updated" within the row, but the underlying $O(n)$-space idea still holds once that bookkeeping is handled.

8. Applications & Alternatives

When the grid is very large but mostly free of obstacles, the closed-form binomial count or a straight-line cost estimate can replace the full table; when obstacles or resource constraints are unpredictable, or the grid is sparse, a graph search such as Dijkstra's algorithm over grid cells as graph nodes is a reasonable alternative to a hand-written DP table, especially if costs are not uniform per step.

9. Exercises and Mastery

Easy

1. Compute the number of unique paths for a 4×5 grid by hand, filling the DP table row by row, and check it against the binomial formula.

Medium

1. Combine Minimum Path Sum with obstacles: extend the minimum-cost-path recurrence so that an obstacle cell is simply unreachable (treat its cost as infinite instead of zero, since here you are minimizing rather than counting). Work out how the first row and first column must change.

Hard

1. Sketch the state for "Cherry Pickup": two people start at opposite corners of a grid and walk toward each other (or the same corner-to-corner path twice), collecting cherries, where a cell's cherry can only be collected once even if both people pass through it. A direct state is $(r_1, c_1, r_2, c_2)$, four dimensions; since both walkers take the same number of steps to reach any position, $r_1 + c_1 = r_2 + c_2$ always holds, so one coordinate is redundant and the state reduces to $(\text{steps}, c_1, c_2)$, three dimensions. Describe the transition rule at a shared cell without necessarily writing full code.

Review rhythm: tomorrow, re-derive the Unique Paths and Minimum Cost Path recurrences from a blank page; next week, implement the obstacle variant from memory and check the first-row/first-column edge case by hand; several weeks later, work through the Dungeon Game backward-computation argument again without looking, then find one more multi-state grid problem and identify what its extra state dimension must be.

10. Summary Cheat Sheet

• Grid DP states are cells $(r, c)$; the recurrence usually combines the cell above and the cell to the left.
• Unique Paths: $dp[r][c] = dp[r-1][c] + dp[r][c-1]$, with a closed-form $\binom{m+n-2}{m-1}$ alternative when there are no obstacles.
• Minimum Cost Path: $dp[r][c] = grid[r][c] + \min(dp[r-1][c], dp[r][c-1])$.
• Obstacles: a blocked cell is always 0 (or infinite cost), and treating the whole table — including row 0 and column 0 — with one uniform rule avoids special-casing the edges incorrectly.
• Multi-state grid DP extends the state to $(r, c, \text{extra})$ when the transition depends on more than position, as in Dungeon Game's remaining health or Cherry Pickup's second walker.
• Dungeon-Game-style "minimum required" problems must be filled backward, from the goal toward the start, because the requirement at a cell depends on what lies ahead of it.
• Standard grid DP is $O(m \times n)$ time and space; when only the previous row matters, space reduces to $O(n)$ with a rolling array.