LeetCode Patterns ·

🎯 DP - Grid

1️⃣ Core Framework

When discussing Grid DP, I frame it as:

What problem pattern grid DP solves
Cell state definition
Movement direction
Unique paths
Minimum path sum
Obstacles
Triangle DP
Dungeon game
Space optimization
Senior-level explanation

2️⃣ What Problem Are We Solving?

Grid DP is used when the input is a 2D matrix and the answer for each cell depends on nearby cells.

It is commonly used for:

Unique Paths
Unique Paths II
Minimum Path Sum
Triangle
Dungeon Game
Maximal Square
Minimum Falling Path Sum
Cherry Pickup variants
Path counting
Path optimization
2D sequence transition problems

The core idea is:

Define dp[r][c] as the answer for cell (r, c),
then compute it from neighboring cells.

👉 Interview Answer

Grid DP is used when the problem is on a 2D matrix and each cell can be computed from nearby cells.

The key is to define what dp[r][c] means, understand the allowed movement directions, set the boundary conditions, and fill the table in an order where dependencies are already computed.

3️⃣ Basic Grid DP Model

Common State

Most grid DP problems use:

dp[r][c] = answer related to cell (r, c)

Depending on the problem, this can mean:

number of ways to reach (r, c)
minimum cost to reach (r, c)
maximum score ending at (r, c)
size of square ending at (r, c)
minimum health needed starting from (r, c)

Common Movement

Most basic grid DP allows:

right
down

or reverse:

from top
from left

Typical Recurrence

If movement is only right and down, then to reach (r, c):

come from top:  (r - 1, c)
come from left: (r, c - 1)

So:

dp[r][c] = combine(dp[r - 1][c], dp[r][c - 1])

👉 Interview Answer

In grid DP, I treat each cell as a subproblem.

If movement is only right and down, then each cell can only be reached from the top or from the left.

So the recurrence usually combines dp[r - 1][c] and dp[r][c - 1].

4️⃣ Why Iteration Order Matters

Dependency Direction

If:

dp[r][c] depends on top and left

Then we should iterate:

top to bottom
left to right

Example

for r in range(rows):
    for c in range(cols):
        compute dp[r][c]

By the time we reach (r, c):

dp[r - 1][c] is already computed
dp[r][c - 1] is already computed

Reverse Direction

Some problems depend on:

right
down

Then we may need to iterate:

bottom to top
right to left

Example:

Dungeon Game

👉 Interview Answer

The iteration order must respect dependencies.

If dp[r][c] depends on top and left, I iterate from top-left to bottom-right.

If dp[r][c] depends on right and down, I iterate from bottom-right to top-left.

A wrong iteration order can use states before they are computed.

5️⃣ Unique Paths

Problem

A robot starts at the top-left corner and wants to reach the bottom-right corner.

It can only move:

right
down

Return the number of unique paths.

State Definition

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

Recurrence

To reach (r, c):

from top
or
from left

So:

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

Code

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

    for r in range(m):
        dp[r][0] = 1

    for c in range(n):
        dp[0][c] = 1

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

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

👉 Interview Answer

For Unique Paths, I define dp[r][c] as the number of ways to reach cell r, c.

Since the robot can only move right or down, each cell can only be reached from the top or left.

The first row and first column each have exactly one path.

6️⃣ Unique Paths Space Optimization

Observation

For each row:

dp[c] = number of ways to reach current row, column c

When updating dp[c]:

dp[c] already represents top
dp[c - 1] represents left

So:

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

Code

def unique_paths(m, n):
    dp = [1] * n

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

    return dp[-1]

Complexity

Time: O(mn)
Space: O(n)

👉 Interview Answer

Unique Paths can be optimized to one row.

dp[c] represents the number of ways to reach column c in the current row.

Before update, dp[c] is the value from the top.

dp[c - 1] is the value from the left.

So dp[c] += dp[c - 1].

7️⃣ Unique Paths II

Problem

Same as Unique Paths, but some cells contain obstacles.

An obstacle blocks the path.

State Definition

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

If cell (r, c) is obstacle:

dp[r][c] = 0

Code

def unique_paths_with_obstacles(obstacle_grid):
    rows = len(obstacle_grid)
    cols = len(obstacle_grid[0])

    dp = [[0] * cols for _ in range(rows)]

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

    dp[0][0] = 1

    for r in range(rows):
        for c in range(cols):
            if obstacle_grid[r][c] == 1:
                dp[r][c] = 0
                continue

            if r > 0:
                dp[r][c] += dp[r - 1][c]

            if c > 0:
                dp[r][c] += dp[r][c - 1]

    return dp[rows - 1][cols - 1]

Key Insight

Obstacle cells contribute zero paths.

👉 Interview Answer

Unique Paths II is the same path-counting DP with obstacles.

If a cell is blocked, dp[r][c] is zero.

Otherwise, the number of ways comes from the top and left cells.

I also check whether the start cell is blocked.

8️⃣ Minimum Path Sum

Problem

Given a grid of non-negative numbers, find a path from top-left to bottom-right with minimum sum.

You can only move:

right
down

State Definition

dp[r][c] = minimum path sum to reach cell (r, c)

Recurrence

To reach (r, c):

min path from top
or
min path from left

So:

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

Code

def min_path_sum(grid):
    rows = len(grid)
    cols = len(grid[0])

    dp = [[0] * cols for _ in range(rows)]

    dp[0][0] = grid[0][0]

    for r in range(1, rows):
        dp[r][0] = dp[r - 1][0] + grid[r][0]

    for c in range(1, cols):
        dp[0][c] = dp[0][c - 1] + grid[0][c]

    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]

👉 Interview Answer

For Minimum Path Sum, I define dp[r][c] as the minimum cost to reach cell r, c.

Since we can only come from top or left, the recurrence takes the minimum of those two previous states, then adds the current grid value.

9️⃣ Minimum Path Sum In-Place

Why In-Place Works

If modifying the input grid is allowed, we can use grid itself as the DP table.

Code

def min_path_sum(grid):
    rows = len(grid)
    cols = len(grid[0])

    for r in range(1, rows):
        grid[r][0] += grid[r - 1][0]

    for c in range(1, cols):
        grid[0][c] += grid[0][c - 1]

    for r in range(1, rows):
        for c in range(1, cols):
            grid[r][c] += min(grid[r - 1][c], grid[r][c - 1])

    return grid[rows - 1][cols - 1]

Complexity

Time: O(mn)
Extra Space: O(1)

👉 Interview Answer

If input mutation is allowed, I can store the minimum path sum directly in the grid.

Each cell is updated to mean the minimum cost to reach that cell.

This reduces extra space to O(1).

🔟 Triangle

Problem

Given a triangle array, find the minimum path sum from top to bottom.

At each step, you may move to adjacent numbers on the row below.

Example:

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

Answer:

2 + 3 + 5 + 1 = 11

State Definition

dp[r][c] = minimum path sum to reach triangle[r][c]

Bottom-Up Insight

It is often easier to compute from bottom to top.

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

Code

def minimum_total(triangle):
    dp = triangle[-1][:]

    for r in range(len(triangle) - 2, -1, -1):
        for c in range(len(triangle[r])):
            dp[c] = triangle[r][c] + min(dp[c], dp[c + 1])

    return dp[0]

👉 Interview Answer

Triangle can be solved bottom-up.

I start from the last row as the initial DP state.

For each cell above, the best path is its value plus the minimum of the two adjacent states below.

This avoids special boundary handling.

1️⃣1️⃣ Minimum Falling Path Sum

Problem

Given an n x n matrix, find the minimum falling path sum.

From each cell, you may move to:

down
down-left
down-right

State Definition

dp[r][c] = minimum falling path sum ending at cell (r, c)

Recurrence

To reach (r, c):

from (r - 1, c)
from (r - 1, c - 1)
from (r - 1, c + 1)

So:

dp[r][c] = matrix[r][c] + min(previous valid cells)

Code

def min_falling_path_sum(matrix):
    n = len(matrix)

    dp = [row[:] for row in matrix]

    for r in range(1, n):
        for c in range(n):
            best_prev = dp[r - 1][c]

            if c > 0:
                best_prev = min(best_prev, dp[r - 1][c - 1])

            if c + 1 < n:
                best_prev = min(best_prev, dp[r - 1][c + 1])

            dp[r][c] += best_prev

    return min(dp[-1])

👉 Interview Answer

For Minimum Falling Path Sum, I define dp[r][c] as the minimum path sum ending at cell r, c.

Each cell can be reached from the cell above, above-left, or above-right.

The answer is the minimum value in the last row.

1️⃣2️⃣ Maximal Square

Problem

Given a binary matrix, find the area of the largest square containing only 1s.

State Definition

dp[r][c] = side length of the largest square ending at cell (r, c)

Here, ending at (r, c) means (r, c) is the bottom-right corner of the square.

Recurrence

If matrix[r][c] is "1":

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

If matrix[r][c] is "0":

dp[r][c] = 0

Code

def maximal_square(matrix):
    if not matrix or not matrix[0]:
        return 0

    rows = len(matrix)
    cols = len(matrix[0])

    dp = [[0] * cols for _ in range(rows)]
    max_side = 0

    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == "1":
                if r == 0 or c == 0:
                    dp[r][c] = 1
                else:
                    dp[r][c] = 1 + min(
                        dp[r - 1][c],
                        dp[r][c - 1],
                        dp[r - 1][c - 1]
                    )

                max_side = max(max_side, dp[r][c])

    return max_side * max_side

👉 Interview Answer

For Maximal Square, I define dp[r][c] as the side length of the largest all-one square whose bottom-right corner is r, c.

If the current cell is 1, the square size depends on the minimum of top, left, and top-left.

The final area is max side length squared.

1️⃣3️⃣ Dungeon Game

Problem

A knight starts at the top-left cell and must rescue the princess at the bottom-right cell.

Each cell can increase or decrease health.

The knight must always have at least 1 health.

Return the minimum initial health needed.

Why Forward DP Is Hard

If we compute from start to end, the current path sum is not enough.

We need to know:

minimum health needed for the future

So it is easier to compute backward.

State Definition

dp[r][c] = minimum health needed before entering cell (r, c)

Recurrence

To survive after entering cell (r, c):

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

But health must be at least 1:

dp[r][c] = max(1, need)

Code

def calculate_minimum_hp(dungeon):
    rows = len(dungeon)
    cols = len(dungeon[0])

    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):
        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]

👉 Interview Answer

Dungeon Game is a reverse grid DP problem.

I define dp[r][c] as the minimum health required before entering cell r, c.

Since future survival matters, I compute from bottom-right to top-left.

At each cell, I choose the better of right or down, subtract the current cell value, and ensure health is at least 1.

1️⃣4️⃣ Cherry Pickup Style Problems

Problem Pattern

Some grid DP problems involve two people moving through the grid at the same time.

Examples:

Cherry Pickup
Cherry Pickup II

Key Idea

Instead of thinking of one person going forward and then returning, model it as:

two walkers moving simultaneously

State Example

For two walkers:

dp[row][col1][col2]

means:

maximum cherries collected when walker 1 is at col1
and walker 2 is at col2 on the same row

Why This Works

The two paths are coupled.

A single walker state is not enough.

We need both positions to avoid double-counting and coordinate movement.

👉 Interview Answer

For Cherry Pickup-style problems, I often model two paths as two walkers moving simultaneously.

The DP state must include both positions.

If both walkers land on the same cell, we count that cell once.

This turns a hard path interaction problem into a multi-dimensional grid DP.

1️⃣5️⃣ Grid DP With Obstacles

Common Pattern

If a cell is blocked:

dp[r][c] = invalid

Depending on the problem:

0 ways
infinity cost
cannot transition through it

Example

Path counting:

if obstacle_grid[r][c] == 1:
    dp[r][c] = 0

Minimum cost:

if blocked:
    dp[r][c] = INF

👉 Interview Answer

In grid DP with obstacles, blocked cells usually become invalid states.

For path counting, invalid means zero ways.

For minimum-cost problems, invalid often means infinity.

I also make sure not to transition from or into blocked cells.

1️⃣6️⃣ Boundary Handling

Common Boundaries

First row:

can only come from left

First column:

can only come from top

Bottom row or right column may matter for reverse DP.

Two Common Approaches

Approach 1: Initialize boundaries manually

for r in range(rows):
    dp[r][0] = ...

Approach 2: Use padding

dp = [[INF] * (cols + 1) for _ in range(rows + 1)]

Padding can simplify recurrence.

👉 Interview Answer

Boundary handling is one of the main sources of grid DP bugs.

I either initialize the first row and first column explicitly, or use padded DP arrays to simplify transitions.

The right approach depends on which one makes the recurrence cleaner.

1️⃣7️⃣ Space Optimization

When It Works

If:

dp[r][c] only depends on current row and previous row

then we can use:

1D dp array

Example

Unique Paths:

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

Minimum Path Sum:

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

Important Detail

In 1D grid DP:

dp[c] often means value from previous row before update
dp[c - 1] means value from current row after update

👉 Interview Answer

Grid DP can often be optimized from O(mn) to O(n) space.

In a 1D DP array, dp[c] usually represents the value from the previous row before update, while dp[c - 1] represents the current row’s left value.

This works when the recurrence only needs top and left.

1️⃣8️⃣ In-Place Grid DP

When It Works

If the input grid does not need to be preserved, we can store DP values directly inside the grid.

Common examples:

Minimum Path Sum
Number of paths if grid is mutable
Some obstacle path problems

When Not To Use

Avoid in-place mutation if:

the original grid is needed later
the interviewer says input should not be modified
the grid contains semantic values that must remain unchanged

👉 Interview Answer

In-place grid DP is possible when modifying the input is allowed.

I update each cell to store the DP value for that cell.

This reduces extra space, but I avoid it if the original grid must be preserved.

1️⃣9️⃣ Complexity Analysis

Standard Grid DP

For an m x n grid:

Time: O(mn)
Space: O(mn)

Because:

each cell is computed once

Space Optimized

If using one row:

Time: O(mn)
Space: O(n)

In-Place

If modifying input:

Time: O(mn)
Extra Space: O(1)

Multi-Dimensional Grid DP

For two-walker problems:

state space may be O(rows * cols * cols)

or more.

👉 Interview Answer

Most basic grid DP problems are O(mn) time because each cell is computed once.

Space is O(mn) with a full table, O(n) with row compression, and O(1) extra space if input can be modified.

Multi-agent grid DP can have higher-dimensional state spaces.

2️⃣0️⃣ Common Edge Cases

Empty Grid

grid = []

Single Cell

grid = [[x]]

Single Row

only move right

Single Column

only move down

Start or End Blocked

For obstacle problems:

if start blocked or end blocked, answer may be 0

Negative Values

For minimum path or dungeon problems, negative values may change the recurrence meaning.

👉 Interview Answer

Common grid DP edge cases include empty grid, single cell, single row, single column, blocked start or end cells, and negative values.

I usually test boundary rows and columns carefully because many bugs happen there.

2️⃣1️⃣ Common Mistakes

Mistake 1: Wrong State Meaning

Confusing:

ways to reach cell

with:

minimum cost to reach cell

Mistake 2: Wrong Iteration Direction

Forward DP cannot always solve reverse-dependency problems.

Example:

Dungeon Game

Mistake 3: Bad Boundary Initialization

First row and first column often need special handling.

Mistake 4: Mishandling Obstacles

Obstacle cells should not contribute transitions.

Mistake 5: Unsafe Space Optimization

Using 1D DP without understanding what dp[c] means before and after update.

Mistake 6: Returning Wrong Cell

Usually answer is:

dp[rows - 1][cols - 1]

But some problems require:

min(dp[last_row])
max over all cells
dp[0][0] in reverse DP

👉 Interview Answer

Common grid DP mistakes include unclear state definition, wrong iteration direction, incorrect boundary initialization, mishandling obstacles, unsafe space optimization, and returning the wrong final state.

I avoid these by defining dp[r][c] clearly before writing recurrence.

2️⃣2️⃣ When Grid DP Applies

Good Fit

Use grid DP when:

input is a 2D matrix
movement directions are constrained
cell answer depends on neighboring cells
problem asks for number of paths
minimum path cost
maximum path score
largest square or rectangle
reverse survival requirement

Problem Signals

Look for words like:

grid
matrix
path from top-left to bottom-right
move right or down
minimum path
unique paths
obstacle
falling path
square
triangle
dungeon

👉 Interview Answer

I consider grid DP when the input is a matrix and each cell’s answer depends on neighboring cells.

Common signals include path counting, minimum path sum, constrained movement, obstacles, falling paths, and square or rectangle problems.

2️⃣3️⃣ When Grid DP Does Not Apply

Not Good Fit

Grid DP may not be ideal when:

movement is arbitrary and shortest path is needed
each move has equal cost and obstacles exist
need connected components
need reachability only
grid changes dynamically

Better Alternatives

Problem Type	Better Pattern
Shortest path unweighted grid	BFS
Weighted shortest path	Dijkstra
Connected regions	DFS / BFS
Dynamic range updates	Segment Tree / BIT
All possible paths explicitly	Backtracking
Union of cells	Union Find

👉 Interview Answer

Grid DP is best when transitions follow a fixed direction and dependencies are acyclic.

If movement is arbitrary in four directions and the task is shortest path, BFS or Dijkstra is usually better.

If the problem is connected components, DFS or BFS is usually more appropriate.

2️⃣4️⃣ Standard Templates

Basic Grid DP Template

def grid_dp(grid):
    rows = len(grid)
    cols = len(grid[0])

    dp = [[0] * cols for _ in range(rows)]

    dp[0][0] = initial_value

    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                continue

            candidates = []

            if r > 0:
                candidates.append(dp[r - 1][c])

            if c > 0:
                candidates.append(dp[r][c - 1])

            dp[r][c] = combine(candidates, grid[r][c])

    return dp[rows - 1][cols - 1]

Path Counting Template

def count_paths(rows, cols):
    dp = [[0] * cols for _ in range(rows)]

    for r in range(rows):
        dp[r][0] = 1

    for c in range(cols):
        dp[0][c] = 1

    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]

Minimum Path Sum Template

def min_path_sum(grid):
    rows = len(grid)
    cols = len(grid[0])

    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]

    for r in range(1, rows):
        dp[r][0] = dp[r - 1][0] + grid[r][0]

    for c in range(1, cols):
        dp[0][c] = dp[0][c - 1] + grid[0][c]

    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[-1][-1]

1D Grid DP Template

def grid_dp_1d(grid):
    rows = len(grid)
    cols = len(grid[0])

    dp = [0] * cols

    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                dp[c] = initial_value
            elif r == 0:
                dp[c] = from_left(dp[c - 1], grid[r][c])
            elif c == 0:
                dp[c] = from_top(dp[c], grid[r][c])
            else:
                dp[c] = combine(dp[c], dp[c - 1], grid[r][c])

    return dp[-1]

Reverse Grid DP Template

def reverse_grid_dp(grid):
    rows = len(grid)
    cols = len(grid[0])

    dp = [[0] * cols for _ in range(rows)]

    for r in range(rows - 1, -1, -1):
        for c in range(cols - 1, -1, -1):
            dp[r][c] = compute_from_right_and_down(r, c)

    return dp[0][0]

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

Grid DP is used when the input is a 2D matrix and each cell represents a subproblem.

The most important step is defining what dp[r][c] means. It can mean the number of ways to reach a cell, the minimum cost to reach a cell, the maximum score ending at a cell, the side length of a square ending at a cell, or the minimum health required before entering a cell.

After defining the state, I identify the allowed movement directions. If movement is only right and down, then each cell usually depends on the top and left cells. In that case, I fill the table from top-left to bottom-right.

If the state depends on future cells, such as right and down, I may need to compute from bottom-right to top-left. Dungeon Game is a classic example of reverse grid DP.

Boundary handling is critical. The first row and first column often need special initialization because they only have one possible predecessor. Another way to simplify boundaries is to use padding with infinity or zero values.

For path-counting problems, the recurrence usually adds ways from neighbors. For minimum-cost problems, the recurrence takes the minimum of previous states and adds the current cell cost. For square problems like Maximal Square, the recurrence may depend on top, left, and top-left.

Obstacles are modeled as invalid states. For counting paths, an obstacle contributes zero ways. For minimum-cost problems, an obstacle can be treated as infinity.

Space can often be optimized from O(mn) to O(n), because each row only depends on the previous row and current row. In a 1D DP array, dp[c] usually represents the value from the previous row before update, while dp[c - 1] represents the current row’s left value.

If input mutation is allowed, some grid DP problems can be solved in-place, reducing extra space to O(1).

The typical complexity is O(mn) time, because each cell is processed once. Space is O(mn) for a full table, O(n) for row compression, or O(1) extra space if done in-place.

At a senior level, I would explain: what each cell state represents, what directions are allowed, which neighboring states are dependencies, why the iteration order is correct, how boundaries and obstacles are handled, and whether space can be safely optimized.

⭐ Final Insight

Grid DP 的核心不是“二维数组填表”。

它的核心是把每个 cell 看成一个 subproblem，并根据 movement direction 建立 dependency。

Senior-level 的重点是：

dp[r][c] 代表什么，当前 cell 依赖哪些 neighbors， iteration order 为什么正确， boundary 如何初始化， obstacle 如何处理， final answer 在哪个 cell，以及是否可以安全地做 1D 或 in-place optimization。

能讲清楚这些， Grid DP 就是一类处理 matrix path、cost、count、square 和 reverse dependency 的核心动态规划模型。

中文部分

🎯 DP - Grid

1️⃣ 核心框架

讨论 Grid DP 时，我通常从：

Grid DP 解决什么问题
Cell state definition
Movement direction
Unique paths
Minimum path sum
Obstacles
Triangle DP
Dungeon game
Space optimization
高级工程师解释方式

2️⃣ 要解决什么问题？

Grid DP 用于输入是 2D matrix，并且每个 cell 的答案依赖附近 cells 的场景。

它常用于：

Unique Paths
Unique Paths II
Minimum Path Sum
Triangle
Dungeon Game
Maximal Square
Minimum Falling Path Sum
Cherry Pickup variants
Path counting
Path optimization
2D sequence transition problems

核心思想是：

定义 dp[r][c] 为 cell (r, c) 的答案，
然后从相邻 cells 推导出来。

👉 面试回答

Grid DP 用于 2D matrix 上的问题。

每个 cell 通常可以看成一个 subproblem。

关键是定义 dp[r][c] 的含义，理解允许的 movement directions，设置 boundary conditions，并按照 dependencies 已经计算好的顺序填表。

3️⃣ Basic Grid DP Model

Common State

大多数 grid DP 使用：

dp[r][c] = 和 cell (r, c) 有关的答案

根据题目不同，它可以表示：

到达 (r, c) 的路径数量
到达 (r, c) 的 minimum cost
以 (r, c) 结尾的 maximum score
以 (r, c) 为右下角的 square size
进入 (r, c) 前需要的 minimum health

Common Movement

基础 grid DP 通常允许：

right
down

反过来看就是：

from top
from left

Typical Recurrence

如果只能 right 和 down，那么到达 (r, c)：

来自 top:  (r - 1, c)
来自 left: (r, c - 1)

所以：

dp[r][c] = combine(dp[r - 1][c], dp[r][c - 1])

👉 面试回答

在 grid DP 中，我把每个 cell 看成一个 subproblem。

如果 movement 只能 right 和 down，那么每个 cell 只能从 top 或 left 到达。

所以 recurrence 通常会 combine dp[r - 1][c] 和 dp[r][c - 1]。

4️⃣ 为什么 Iteration Order 重要？

Dependency Direction

如果：

dp[r][c] depends on top and left

那就应该：

top to bottom
left to right

Example

for r in range(rows):
    for c in range(cols):
        compute dp[r][c]

当来到 (r, c) 时：

dp[r - 1][c] 已经计算好
dp[r][c - 1] 已经计算好

Reverse Direction

有些问题依赖：

right
down

那就可能需要：

bottom to top
right to left

Example:

Dungeon Game

👉 面试回答

Iteration order 必须满足 dependency order。

如果 dp[r][c] 依赖 top 和 left，我会从 top-left 到 bottom-right。

如果 dp[r][c] 依赖 right 和 down，我会从 bottom-right 到 top-left。

错误的遍历顺序会使用还没有计算好的 state。

5️⃣ Unique Paths

Problem

Robot 从 top-left 出发，到达 bottom-right。

只能移动：

right
down

返回 unique paths 数量。

State Definition

dp[r][c] = 到达 cell (r, c) 的路径数量

Recurrence

到达 (r, c)：

from top
or
from left

所以：

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

Code

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

    for r in range(m):
        dp[r][0] = 1

    for c in range(n):
        dp[0][c] = 1

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

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

👉 面试回答

对 Unique Paths，我定义 dp[r][c] 为到达 cell r, c 的路径数量。

因为 robot 只能 right 或 down，所以每个 cell 只能从 top 或 left 到达。

第一行和第一列都只有一种路径。

6️⃣ Unique Paths Space Optimization

Observation

对于每一行：

dp[c] = 到达当前 row、column c 的 ways

更新 dp[c] 时：

dp[c] 原本代表 top
dp[c - 1] 代表 left

所以：

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

Code

def unique_paths(m, n):
    dp = [1] * n

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

    return dp[-1]

Complexity

Time: O(mn)
Space: O(n)

👉 面试回答

Unique Paths 可以优化成一行 DP。

dp[c] 表示当前 row 到达 column c 的 ways。

更新前，dp[c] 是来自 top 的值。

dp[c - 1] 是当前 row 左边的值。

所以 dp[c] += dp[c - 1]。

7️⃣ Unique Paths II

Problem

和 Unique Paths 一样，但 grid 中有 obstacles。

Obstacle 会阻断路径。

State Definition

dp[r][c] = 到达 cell (r, c) 的路径数量

如果 (r, c) 是 obstacle：

dp[r][c] = 0

Code

def unique_paths_with_obstacles(obstacle_grid):
    rows = len(obstacle_grid)
    cols = len(obstacle_grid[0])

    dp = [[0] * cols for _ in range(rows)]

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

    dp[0][0] = 1

    for r in range(rows):
        for c in range(cols):
            if obstacle_grid[r][c] == 1:
                dp[r][c] = 0
                continue

            if r > 0:
                dp[r][c] += dp[r - 1][c]

            if c > 0:
                dp[r][c] += dp[r][c - 1]

    return dp[rows - 1][cols - 1]

Key Insight

Obstacle cells 贡献 0 条路径。

👉 面试回答

Unique Paths II 是带 obstacle 的 path-counting DP。

如果当前 cell 被 blocked， dp[r][c] 就是 0。

否则路径数来自 top 和 left。

还需要检查 start cell 是否被 blocked。

8️⃣ Minimum Path Sum

Problem

给定一个 non-negative grid，找从 top-left 到 bottom-right 的 minimum path sum。

只能移动：

right
down

State Definition

dp[r][c] = 到达 cell (r, c) 的 minimum path sum

Recurrence

到达 (r, c)：

来自 top 的 minimum path
或者
来自 left 的 minimum path

所以：

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

Code

def min_path_sum(grid):
    rows = len(grid)
    cols = len(grid[0])

    dp = [[0] * cols for _ in range(rows)]

    dp[0][0] = grid[0][0]

    for r in range(1, rows):
        dp[r][0] = dp[r - 1][0] + grid[r][0]

    for c in range(1, cols):
        dp[0][c] = dp[0][c - 1] + grid[0][c]

    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]

👉 面试回答

对 Minimum Path Sum，我定义 dp[r][c] 为到达 cell r, c 的 minimum cost。

因为只能从 top 或 left 到达，所以 recurrence 是取这两个 previous states 的 minimum，再加上当前 grid value。

9️⃣ Minimum Path Sum In-Place

为什么可以 In-Place？

如果允许修改 input grid，可以直接把 grid 当成 DP table。

Code

def min_path_sum(grid):
    rows = len(grid)
    cols = len(grid[0])

    for r in range(1, rows):
        grid[r][0] += grid[r - 1][0]

    for c in range(1, cols):
        grid[0][c] += grid[0][c - 1]

    for r in range(1, rows):
        for c in range(1, cols):
            grid[r][c] += min(grid[r - 1][c], grid[r][c - 1])

    return grid[rows - 1][cols - 1]

Complexity

Time: O(mn)
Extra Space: O(1)

👉 面试回答

如果题目允许修改 input，我可以直接在 grid 中存每个 cell 的 minimum path sum。

每个 cell 更新后，含义变成到达该 cell 的最小 cost。

这样可以把 extra space 降到 O(1)。

🔟 Triangle

Problem

给定 triangle array，找从 top 到 bottom 的 minimum path sum。

每一步只能移动到下一行相邻位置。

Example:

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

Answer:

2 + 3 + 5 + 1 = 11

State Definition

dp[r][c] = 到达 triangle[r][c] 的 minimum path sum

Bottom-Up Insight

从 bottom to top 通常更简单。

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

Code

def minimum_total(triangle):
    dp = triangle[-1][:]

    for r in range(len(triangle) - 2, -1, -1):
        for c in range(len(triangle[r])):
            dp[c] = triangle[r][c] + min(dp[c], dp[c + 1])

    return dp[0]

👉 面试回答

Triangle 可以用 bottom-up DP。

我从最后一行开始作为初始 DP。

对上面每个 cell，最优路径等于当前值加上下一行两个相邻位置的较小值。

这样可以避免复杂的 boundary handling。

1️⃣1️⃣ Minimum Falling Path Sum

Problem

给定 n x n matrix，找 minimum falling path sum。

从每个 cell 可以移动到下一行的：

down
down-left
down-right

State Definition

dp[r][c] = 以 cell (r, c) 结尾的 minimum falling path sum

Recurrence

到达 (r, c) 可以来自：

(r - 1, c)
(r - 1, c - 1)
(r - 1, c + 1)

所以：

dp[r][c] = matrix[r][c] + min(previous valid cells)

Code

def min_falling_path_sum(matrix):
    n = len(matrix)

    dp = [row[:] for row in matrix]

    for r in range(1, n):
        for c in range(n):
            best_prev = dp[r - 1][c]

            if c > 0:
                best_prev = min(best_prev, dp[r - 1][c - 1])

            if c + 1 < n:
                best_prev = min(best_prev, dp[r - 1][c + 1])

            dp[r][c] += best_prev

    return min(dp[-1])

👉 面试回答

对 Minimum Falling Path Sum，我定义 dp[r][c] 为以 cell r, c 结尾的 minimum path sum。

当前 cell 可以从正上方、左上方、右上方到达。

最终答案是最后一行的最小值。

1️⃣2️⃣ Maximal Square

Problem

给定 binary matrix，找只包含 1 的最大 square area。

State Definition

dp[r][c] = 以 cell (r, c) 作为 bottom-right corner 的最大 square side length

Recurrence

如果 matrix[r][c] 是 "1"：

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

如果 matrix[r][c] 是 "0"：

dp[r][c] = 0

Code

def maximal_square(matrix):
    if not matrix or not matrix[0]:
        return 0

    rows = len(matrix)
    cols = len(matrix[0])

    dp = [[0] * cols for _ in range(rows)]
    max_side = 0

    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == "1":
                if r == 0 or c == 0:
                    dp[r][c] = 1
                else:
                    dp[r][c] = 1 + min(
                        dp[r - 1][c],
                        dp[r][c - 1],
                        dp[r - 1][c - 1]
                    )

                max_side = max(max_side, dp[r][c])

    return max_side * max_side

👉 面试回答

对 Maximal Square，我定义 dp[r][c] 为以 r, c 作为右下角的最大 all-one square side length。

如果当前 cell 是 1， square size 取决于 top、left 和 top-left 三个方向的最小值。

最终 area 是 max side length 的平方。

1️⃣3️⃣ Dungeon Game

Problem

Knight 从 top-left 出发，要到达 bottom-right 救 princess。

每个 cell 会增加或减少 health。

Knight 的 health 必须始终至少为 1。

返回 minimum initial health。

为什么 Forward DP 难？

从 start 到 end 正向算时，当前 path sum 不够。

我们真正需要知道的是：

未来至少需要多少 health 才能活下去

所以反向计算更自然。

State Definition

dp[r][c] = 进入 cell (r, c) 前需要的 minimum health

Recurrence

为了进入 (r, c) 后还能继续活下去：

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

但 health 至少为 1：

dp[r][c] = max(1, need)

Code

def calculate_minimum_hp(dungeon):
    rows = len(dungeon)
    cols = len(dungeon[0])

    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):
        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]

👉 面试回答

Dungeon Game 是 reverse grid DP。

我定义 dp[r][c] 为进入 cell r, c 前需要的 minimum health。

因为 future survival 更重要，所以从 bottom-right 向 top-left 计算。

对每个 cell，选择 right 或 down 中需要 health 更少的方向，减去当前 cell 的影响，并保证 health 至少为 1。

1️⃣4️⃣ Cherry Pickup Style Problems

Problem Pattern

有些 grid DP 涉及两个人同时在 grid 中移动。

Examples:

Cherry Pickup
Cherry Pickup II

Key Idea

不要把它看成一个人走过去再回来。

可以建模成：

two walkers moving simultaneously

State Example

对于两个 walkers：

dp[row][col1][col2]

表示：

walker 1 在 col1
walker 2 在 col2
并且两人都在同一 row 时，
能收集到的最大 cherries。

Why This Works

两条 path 是互相影响的。

单个 walker 的状态不够。

必须同时记录两个位置，避免 double-counting，并协调 movement。

👉 Interview Answer

For Cherry Pickup-style problems, I often model two paths as two walkers moving simultaneously.

The DP state must include both positions.

If both walkers land on the same cell, that cell is counted once.

This converts a path-interaction problem into a multi-dimensional grid DP.

1️⃣5️⃣ Grid DP With Obstacles

Common Pattern

如果 cell 是 blocked：

dp[r][c] = invalid

根据题目不同：

0 ways
infinity cost
cannot transition through it

Example

Path counting:

if obstacle_grid[r][c] == 1:
    dp[r][c] = 0

Minimum cost:

if blocked:
    dp[r][c] = INF

👉 面试回答

Grid DP 中如果有 obstacles， blocked cells 通常是 invalid states。

对 path counting， invalid 表示 0 ways。

对 minimum-cost problems， invalid 通常表示 infinity。

同时不能从 blocked cell 转移，也不能转移到 blocked cell。

1️⃣6️⃣ Boundary Handling

Common Boundaries

First row:

只能从 left 来

First column:

只能从 top 来

对于 reverse DP， bottom row 或 right column 也可能需要特殊处理。

Two Common Approaches

Approach 1: 手动初始化 boundary

for r in range(rows):
    dp[r][0] = ...

Approach 2: 使用 padding

dp = [[INF] * (cols + 1) for _ in range(rows + 1)]

Padding 可以简化 recurrence。

👉 面试回答

Boundary handling 是 grid DP 最容易出错的地方之一。

我通常有两种方式：第一是手动初始化 first row 和 first column。第二是用 padded DP array 简化边界。

具体选择取决于哪种写法让 recurrence 更清楚。

1️⃣7️⃣ Space Optimization

When It Works

如果：

dp[r][c] 只依赖 current row 和 previous row

就可以使用：

1D dp array

Example

Unique Paths:

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

Minimum Path Sum:

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

Important Detail

在 1D grid DP 中：

dp[c] 更新前通常代表 previous row 的值
dp[c - 1] 通常代表 current row 的 left value

👉 面试回答

Grid DP 经常可以从 O(mn) space 优化到 O(n)。

在 1D DP array 中，更新前的 dp[c] 通常代表上一行的值。

dp[c - 1] 代表当前行左边已经更新过的值。

只要 recurrence 只依赖 top 和 left，这种优化通常是安全的。

1️⃣8️⃣ In-Place Grid DP

When It Works

如果 input grid 不需要保留，可以直接把 DP value 存回 grid。

常见例子：

Minimum Path Sum
Number of paths if grid is mutable
Some obstacle path problems

When Not To Use

不要 in-place mutate，如果：

原始 grid 后面还需要
interviewer 说明不能修改 input
grid 中的语义值必须保留

👉 面试回答

如果题目允许修改 input，可以使用 in-place grid DP。

我会把每个 cell 更新成它对应的 DP value。

这样可以减少 extra space。

但如果原始 grid 需要保留，就不要这样做。

1️⃣9️⃣ Complexity Analysis

Standard Grid DP

对于 m x n grid：

Time: O(mn)
Space: O(mn)

因为：

each cell is computed once

Space Optimized

如果使用一行 DP：

Time: O(mn)
Space: O(n)

In-Place

如果修改 input：

Time: O(mn)
Extra Space: O(1)

Multi-Dimensional Grid DP

对于 two-walker problems：

state space may be O(rows * cols * cols)

甚至更高。

👉 面试回答

大多数基础 grid DP 是 O(mn) time，因为每个 cell 只处理一次。

Full DP table 是 O(mn) space。

Row compression 是 O(n) space。

如果可以 in-place 修改 input， extra space 可以是 O(1)。

多人路径类 grid DP 可能需要更高维 state。

2️⃣0️⃣ 常见 Edge Cases

Empty Grid

grid = []

Single Cell

grid = [[x]]

Single Row

only move right

Single Column

only move down

Start or End Blocked

Obstacle problems 中：

if start blocked or end blocked, answer may be 0

Negative Values

Minimum path 或 Dungeon Game 中， negative values 可能改变 recurrence 的含义。

👉 面试回答

Grid DP 常见 edge cases 包括 empty grid、 single cell、 single row、 single column、 start 或 end 被 blocked，以及 negative values。

我通常会特别测试 boundary rows 和 columns，因为很多 bug 都出现在这里。

2️⃣1️⃣ 常见错误

Mistake 1: State Meaning 错误

混淆：

到达 cell 的 ways

和：

到达 cell 的 minimum cost

Mistake 2: Iteration Direction 错误

正向 DP 不一定能解决 reverse-dependency problem。

Example:

Dungeon Game

Mistake 3: Boundary 初始化错误

First row 和 first column 经常需要特殊处理。

Mistake 4: Obstacles 处理错误

Obstacle cells 不应该贡献 transition。

Mistake 5: Space Optimization 不安全

没有理解 1D DP 中 dp[c] 更新前后含义。

Mistake 6: 返回错误位置

通常答案是：

dp[rows - 1][cols - 1]

但有些题需要：

min(dp[last_row])
max over all cells
reverse DP 中的 dp[0][0]

👉 面试回答

Grid DP 常见错误包括： state definition 不清楚、 iteration direction 错误、 boundary initialization 错误、 obstacles 处理错误、不安全的 space optimization、以及返回错误 final state。

我会先明确 dp[r][c] 的含义，再写 recurrence。

2️⃣2️⃣ 什么时候 Grid DP 适用？

Good Fit

当问题满足：

input is a 2D matrix
movement directions are constrained
cell answer depends on neighboring cells
problem asks for number of paths
minimum path cost
maximum path score
largest square or rectangle
reverse survival requirement

Problem Signals

看到这些关键词想到 grid DP：

grid
matrix
path from top-left to bottom-right
move right or down
minimum path
unique paths
obstacle
falling path
square
triangle
dungeon

👉 面试回答

当 input 是 matrix，并且每个 cell 的答案依赖 neighboring cells 时，我会考虑 grid DP。

常见信号包括 path counting、minimum path sum、 constrained movement、obstacles、falling path、以及 square 或 rectangle 问题。

2️⃣3️⃣ 什么时候 Grid DP 不适用？

Not Good Fit

Grid DP 可能不适合：

movement is arbitrary and shortest path is needed
each move has equal cost and obstacles exist
need connected components
need reachability only
grid changes dynamically

Better Alternatives

Problem Type	Better Pattern
Shortest path unweighted grid	BFS
Weighted shortest path	Dijkstra
Connected regions	DFS / BFS
Dynamic range updates	Segment Tree / BIT
All possible paths explicitly	Backtracking
Union of cells	Union Find

👉 面试回答

Grid DP 最适合 movement 有固定方向，并且 dependencies 是 acyclic 的问题。

如果四个方向都能任意移动，并且任务是 shortest path， BFS 或 Dijkstra 通常更合适。

如果问题是 connected components， DFS 或 BFS 更合适。

2️⃣4️⃣ 标准模板

Basic Grid DP Template

def grid_dp(grid):
    rows = len(grid)
    cols = len(grid[0])

    dp = [[0] * cols for _ in range(rows)]

    dp[0][0] = initial_value

    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                continue

            candidates = []

            if r > 0:
                candidates.append(dp[r - 1][c])

            if c > 0:
                candidates.append(dp[r][c - 1])

            dp[r][c] = combine(candidates, grid[r][c])

    return dp[rows - 1][cols - 1]

Path Counting Template

def count_paths(rows, cols):
    dp = [[0] * cols for _ in range(rows)]

    for r in range(rows):
        dp[r][0] = 1

    for c in range(cols):
        dp[0][c] = 1

    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]

Minimum Path Sum Template

def min_path_sum(grid):
    rows = len(grid)
    cols = len(grid[0])

    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]

    for r in range(1, rows):
        dp[r][0] = dp[r - 1][0] + grid[r][0]

    for c in range(1, cols):
        dp[0][c] = dp[0][c - 1] + grid[0][c]

    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[-1][-1]

1D Grid DP Template

def grid_dp_1d(grid):
    rows = len(grid)
    cols = len(grid[0])

    dp = [0] * cols

    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                dp[c] = initial_value
            elif r == 0:
                dp[c] = from_left(dp[c - 1], grid[r][c])
            elif c == 0:
                dp[c] = from_top(dp[c], grid[r][c])
            else:
                dp[c] = combine(dp[c], dp[c - 1], grid[r][c])

    return dp[-1]

Reverse Grid DP Template

def reverse_grid_dp(grid):
    rows = len(grid)
    cols = len(grid[0])

    dp = [[0] * cols for _ in range(rows)]

    for r in range(rows - 1, -1, -1):
        for c in range(cols - 1, -1, -1):
            dp[r][c] = compute_from_right_and_down(r, c)

    return dp[0][0]

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Grid DP 用于 input 是 2D matrix 的问题，每个 cell 都可以看成一个 subproblem。

最重要的第一步是定义 dp[r][c] 的含义。它可以表示到达某个 cell 的 ways，到达某个 cell 的 minimum cost，以某个 cell 结尾的 maximum score，以某个 cell 为右下角的 square side length，或进入某个 cell 之前所需的 minimum health。

定义 state 后，我会确认 allowed movement directions。如果只能 right 和 down，那么每个 cell 通常依赖 top 和 left。这种情况下， table 应该从 top-left 到 bottom-right 填。

如果当前 state 依赖 future cells，比如 right 和 down，就可能需要从 bottom-right 到 top-left 反向计算。 Dungeon Game 是经典 reverse grid DP。

Boundary handling 非常重要。 First row 和 first column 通常需要特殊初始化，因为它们只有一个 predecessor。另一种方式是使用 padding，通过 infinity 或 zero 来简化 recurrence。

对 path-counting problems， recurrence 通常是把 neighboring ways 相加。对 minimum-cost problems， recurrence 通常是取 previous states 的 minimum，再加当前 cell cost。对 Maximal Square 这种 square problem， recurrence 可能依赖 top、left 和 top-left 三个方向。

Obstacles 通常被建模成 invalid states。对 path counting， obstacle 贡献 0 ways。对 minimum-cost problems， obstacle 可以用 infinity 表示。

Grid DP 经常可以从 O(mn) space 优化到 O(n)，因为当前 row 通常只依赖 previous row 和 current row。在 1D DP array 中， dp[c] 更新前通常代表 previous row 的值， dp[c - 1] 代表 current row 左侧已经更新过的值。

如果允许修改 input，有些 grid DP 可以 in-place 完成，把每个 cell 直接更新成对应的 DP value，从而把 extra space 降到 O(1)。

典型复杂度是 O(mn) time，因为每个 cell 处理一次。 Space 可以是 O(mn)、O(n)，或者 in-place 的 O(1) extra space。

高级工程师解释 grid DP 时，我会讲清楚：每个 cell state 表示什么， movement directions 是什么，当前 cell 依赖哪些 neighboring states，为什么 iteration order 正确， boundary 和 obstacles 如何处理，以及是否能安全地 optimize space。

⭐ Final Insight

Grid DP 的核心不是“二维数组填表”。

它的核心是把每个 cell 看成一个 subproblem，并根据 movement direction 建立 dependency。

Senior-level 的重点是：

dp[r][c] 代表什么，当前 cell 依赖哪些 neighbors， iteration order 为什么正确， boundary 如何初始化， obstacle 如何处理， final answer 在哪个 cell，以及是否可以安全地做 1D 或 in-place optimization。

能讲清楚这些， Grid DP 就是一类处理 matrix path、cost、count、square 和 reverse dependency 的核心动态规划模型。