Dynamic Programming on 2D Grids: How to Think About Unique Paths and Minimum Path Sum

Why 2D grid DP shows up so often in interviews

2D grid problems are one of the cleanest ways interviewers test whether you can turn a story into a state transition. The setup is usually simple: you stand on a cell in a matrix, move only right or down, and need to count paths, minimize cost, or maximize score. What makes these problems valuable is that they expose the core DP skill: identify overlapping subproblems and build the answer from smaller states.

If you can solve grid DP well, you are also building muscle for a wider class of problems: path counting, route optimization, obstacle handling, and even string DP when the state becomes two-dimensional for a different reason. The pattern is common enough that you should recognize it quickly during interviews.

In this post, we’ll focus on the two classics:

• Unique Paths: count how many ways you can move from the top-left to the bottom-right.
• Minimum Path Sum: find the least costly path through a grid of weights.

These two problems look different on the surface, but they share the same DP structure.

Problem statement

1) Unique Paths

You are given an m x n grid. Starting at the top-left corner (0, 0), you can move only right or down. How many distinct paths lead to the bottom-right corner (m-1, n-1)?

Example:

m = 3, n = 7

Answer: 28

2) Minimum Path Sum

You are given an m x n grid of non-negative integers. Starting at the top-left corner, you can move only right or down. Find the minimum sum of values along a path to the bottom-right corner.

Example:

grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]

Answer: 7 via 1 → 3 → 1 → 1 → 1

Intuition: the grid as a dependency graph

The key insight is that each cell depends only on the cells directly above it and to the left of it.

For a cell (r, c):

• You can arrive from (r-1, c) by moving down.
• You can arrive from (r, c-1) by moving right.

That means you do not need to explore all possible paths recursively if you already know the best or total result for the smaller subproblems.

Generic DP state

Define dp[r][c] as the answer for the subproblem ending at cell (r, c).

Then the transition usually looks like this:

• Counting paths: dp[r][c] = dp[r-1][c] + dp[r][c-1]
• Minimizing cost: dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])

The exact meaning of dp[r][c] changes, but the shape of the recurrence stays the same.

Why top-left to bottom-right works

This is a natural order because each cell depends only on already-computed cells. If you fill the table row by row or column by column, dependencies are always available.

That is the basic pattern behind 2D DP on grids:

1. Define a state for each cell.
2. Identify transitions from top and left.
3. Set boundary conditions for the first row and first column.
4. Fill the table in a valid order.

Step-by-step approach

Example 1: Unique Paths with a full DP table

Let’s solve the counting version first because it is the simplest grid DP.

State definition

dp[r][c] = number of ways to reach cell (r, c).

Recurrence

To get to (r, c), you must come from above or left:

dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

Base cases

• dp[0][0] = 1 because there is exactly one way to start there.
• First row: only one way to move right repeatedly.
• First column: only one way to move down repeatedly.

Python solution

def unique_paths(m: int, n: int) -> int:
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1

    for r in range(m):
        for c in range(n):
            if r == 0 and c == 0:
                continue
            from_top = dp[r - 1][c] if r > 0 else 0
            from_left = dp[r][c - 1] if c > 0 else 0
            dp[r][c] = from_top + from_left

    return dp[m - 1][n - 1]

Trace on a 3 x 3 grid

The table evolves like this:

1 1 1
1 2 3
1 3 6

Interpretation:

• Cell (0, 1) has 1 way: move right.
• Cell (1, 1) has 2 ways: right then down, or down then right.
• Cell (2, 2) has 6 ways total.

This kind of table is where a visual walkthrough helps. You can literally see the counts accumulate from top and left.

Example 2: Unique Paths with obstacle handling

A common interview follow-up is to add obstacles. The rule becomes: you cannot step on blocked cells.

State definition

Same as before: dp[r][c] = number of ways to reach (r, c).

Modified recurrence

If a cell is blocked, its value is 0. Otherwise:

dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

Python solution

def unique_paths_with_obstacles(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]

    if grid[0][0] == 1:
        return 0

    dp[0][0] = 1

    for r in range(m):
        for c in range(n):
            if grid[r][c] == 1:
                dp[r][c] = 0
                continue
            if r == 0 and c == 0:
                continue

            from_top = dp[r - 1][c] if r > 0 else 0
            from_left = dp[r][c - 1] if c > 0 else 0
            dp[r][c] = from_top + from_left

    return dp[m - 1][n - 1]

What changed?

Only the base logic around blocked cells. The core DP idea stayed the same.

This is important in interviews: once you see the recurrence, many variants become small edits rather than brand-new problems.

Example 3: Minimum Path Sum

Now let’s switch from counting to optimization.

State definition

dp[r][c] = minimum sum needed to reach (r, c).

Recurrence

To reach (r, c), you choose the cheaper of the two ways in:

dp[r][c] = grid[r][c] + min(dp[r - 1][c], dp[r][c - 1])

Base cases

• dp[0][0] = grid[0][0]
• First row: can only come from the left
• First column: can only come from above

Python solution

def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]

    for r in range(m):
        for c in range(n):
            if r == 0 and c == 0:
                continue
            from_top = dp[r - 1][c] if r > 0 else float('inf')
            from_left = dp[r][c - 1] if c > 0 else float('inf')
            dp[r][c] = grid[r][c] + min(from_top, from_left)

    return dp[m - 1][n - 1]

Trace on the sample grid

Input:

1 3 1
1 5 1
4 2 1

DP table:

1 4 5
2 7 6
6 8 7

Explanation:

• (0, 1) = 1 + 3 = 4
• (1, 0) = 1 + 1 = 2
• (1, 1) = 5 + min(4, 2) = 7
• (2, 2) = 1 + min(6, 8) = 7

The final answer is 7.

Space optimization: 2D DP to 1D DP

You do not always need the whole grid. Since each cell depends only on the current row and the previous row, you can compress space to one row.

This is a useful interview optimization when memory matters.

1D Unique Paths

def unique_paths_1d(m: int, n: int) -> int:
    dp = [1] * n

    for _ in range(1, m):
        for c in range(1, n):
            dp[c] += dp[c - 1]

    return dp[-1]

Why this works

• dp[c] holds the value from the row above before it gets updated.
• dp[c - 1] holds the current row’s left value.
• Adding them gives the current cell.

1D Minimum Path Sum

def min_path_sum_1d(grid):
    m, n = len(grid), len(grid[0])
    dp = [float('inf')] * n
    dp[0] = 0

    for r in range(m):
        for c in range(n):
            if c == 0:
                dp[c] = dp[c] + grid[r][c]
            else:
                dp[c] = grid[r][c] + min(dp[c], dp[c - 1])

    return dp[-1]

Complexity comparison

How to recognize this pattern in interviews

Grid DP problems often include phrases like:

• “You can move only right and down”
• “Count the number of ways”
• “Find the minimum cost path”
• “Each cell has a value/weight”
• “There are obstacles or blocked cells”

When you see this, ask yourself:

1. What does dp[r][c] mean?
2. What are the valid incoming states?
3. What happens on the first row and first column?
4. Is the goal to count, minimize, or maximize?

If you can answer those four questions, the code is usually straightforward.

Common interview mistakes

• Forgetting base cases: first row and first column often need special handling.
• Mixing up state meaning: always define whether dp stores count, cost, or best score.
• Using recursion without memoization: this usually leads to exponential time.
• Not handling obstacles or blocked cells carefully: blocked cells should contribute zero paths or be skipped.
• Off-by-one indexing errors: decide whether your DP table mirrors the input exactly or uses padding.

Related problems

2D grid DP is a gateway to many interview classics. Once you understand the pattern, you can extend it to these variants:

• Unique Paths II — obstacles in the grid
• Minimum Path Sum — weighted shortest path in a restricted grid
• Dungeon Game — reverse DP from bottom-right to top-left
• Cherry Pickup — two agents on a grid, often a harder 2D/3D DP
• Triangle — a triangular grid version of the same dependency idea
• Longest Common Subsequence — 2D DP with different meaning for the axes

Notice that the core skill is not memorizing formulas. It is learning to define a state and reason about dependencies.

Key takeaways

• Grid DP is about turning a cell-based problem into a recurrence over top and left neighbors.
• The two most common objectives are counting paths and minimizing path cost.
• Base cases matter a lot, especially the first row and first column.
• A 2D table is easiest to reason about; a 1D array is a useful optimization.
• Once you know the pattern, many variations become small edits to the same template.

If you want to trace the table updates and variable values step by step, I built an interactive version of this walkthrough at codebrew.ai — might help if you’re a visual learner.

Practice these next

1. Unique Paths II
2. Minimum Path Sum
3. Dungeon Game
4. Triangle
5. Cherry Pickup