Grid DP

What is this?

A cell in a grid DP answers one question: what is the best (or the count) for reaching exactly here? Because movement is restricted — usually down and right — a cell can only be reached from a small, fixed set of neighbours, so the recurrence is a combination of two or three values you have already computed.

The interesting problems in this chapter are the ones where the grid is not given to you. Interleaving String has no grid at all in its statement, and becomes trivial the moment you realise its two axes are the two source strings.

💡 Fun fact: Cherry Pickup II is the clearest demonstration that a state can hold more than one position. Two robots move down the grid simultaneously, so the state is (row, column of robot 1, column of robot 2) — a three-dimensional table. Running two independent single-robot passes gives the wrong answer, because the robots interact: they must not both collect from the same cell. Once both positions live in the state, the interaction is handled by a single if col1 == col2 in the value calculation.

🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: identify which cells can legally precede this one, combine their answers, and fill the table in an order that guarantees every predecessor is already computed. When two things move at once, both positions belong in the state.

1. The base pattern, with obstacles

dp = [[0] * n for _ in range(m)]
dp[0][0] = 1 if grid[0][0] == 0 else 0
for r in range(m):
    for c in range(n):
        if grid[r][c] == 1:
            dp[r][c] = 0                       # an obstacle is reachable zero ways
            continue
        if r > 0: dp[r][c] += dp[r-1][c]
        if c > 0: dp[r][c] += dp[r][c-1]

Obstacles need no special machinery — they are simply cells whose answer is zero, and the zero propagates naturally to everything downstream. Setting them to zero rather than skipping them is what keeps the recurrence uniform.

2. A constraint on which predecessor is allowed

Minimum Falling Path Sum II forbids using the same column twice in consecutive rows. The naive fix scans the previous row for each cell, which is O(n²) per row. The better version precomputes the smallest and second-smallest values of the previous row: any cell can use the smallest, unless the smallest came from its own column, in which case it uses the second-smallest. That drops the row cost to O(n).

This "keep the best two so the excluded case still has an answer" trick generalises to any problem where one specific predecessor is forbidden.

3. When the grid is implicit

Interleaving String asks whether s3 is an interleaving of s1 and s2. Let dp[i][j] mean "the first i characters of s1 and the first j of s2 can interleave to form the first i+j of s3". Now it is a grid:

dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1])
        or (dp[i][j-1] and s2[j-1] == s3[i+j-1])

The length check len(s1) + len(s2) == len(s3) is a mandatory early exit; without it the table is the wrong shape and the answer is meaningless.

4. A 30-second worked example (Unique Paths II)

grid (1 = obstacle)        dp table
0 0 0                      1 1 1
0 1 0        →             1 0 1
0 0 0                      1 1 2

dp[1][1] = 0             obstacle
dp[1][2] = dp[0][2] + dp[1][1] = 1 + 0 = 1
dp[2][2] = dp[1][2] + dp[2][1] = 1 + 1 = 2

Two paths reach the corner, and the obstacle's zero propagated correctly without a single special case in the loop.

5. Where you'll actually meet this

• Robotics and warehouse routing. Cheapest path through a cost grid with blocked cells.
• Multi-agent planning. Two pickers, drones or vehicles moving simultaneously is the three-dimensional state exactly.
• Sequence alignment. Interleaving, edit distance and longest common subsequence are all two-string grids.
• Image processing. Seam carving finds a minimum-cost vertical path through an energy grid — a falling-path problem.
• Game AI. Board evaluation over reachable positions with movement rules.

6. Problems in this chapter

▶ Unique Paths II

Count paths from corner to corner with obstacles. Obstacles are cells with zero ways.
Pattern: additive grid DP. Target: O(mn) time, O(n) space with a rolling row.

▶ Bomb Enemy

Most enemies killable by one bomb, given walls blocking the blast. Precompute row and column kill counts in a sweep rather than re-scanning per cell.
Pattern: precomputed directional sums. Target: O(mn) time.

▶ Minimum Falling Path Sum II

Minimum falling path where consecutive rows must use different columns. Keep the smallest and second-smallest of each row.
Pattern: grid DP with an excluded predecessor. Target: O(mn) time, O(n) space.

▶ Cherry Pickup II

Two robots descend the grid collecting cherries. State is (row, col1, col2), with a col1 == col2 check so a shared cell is not double-counted.
Pattern: multi-agent grid DP. Target: O(m · n²) time.

▶ Interleaving String

Decide whether s3 interleaves s1 and s2. A grid whose axes are the two source strings.
Pattern: two-sequence grid DP. Target: O(mn) time, O(n) space.

7. Common pitfalls 🚫

• Skipping obstacle cells instead of zeroing them. Zero keeps the recurrence uniform and propagates correctly.
• An obstacle at the start or end. Both make the answer zero, and both are easy to miss.
• Rescanning the previous row in the falling-path problem. Keep the best two values instead.
• Running two independent passes for the two robots. They interact; both positions must be in one state.
• Double-counting a shared cell when the robots occupy the same column.
• Missing the length check in Interleaving String — without it the DP is nonsense.
• Rolling the row in the wrong direction. When compressing to one row, the iteration order determines whether you read the old value or the new one; get it wrong and the recurrence silently changes.

8. Key takeaways

1. A cell's answer composes from its legal predecessors. Identify them and the recurrence is written.
2. Obstacles are zeros, not special cases.
3. Keep the best two when one predecessor may be forbidden.
4. Simultaneous movers share one state. Independent passes miss the interaction.
5. Grids appear where no grid is mentioned — two strings are two axes.
6. Roll to one row for O(n) space, and watch the iteration direction when you do.
7. Why interviewers like it: the table is easy to describe and hard to get exactly right, and the multi-agent variant cleanly separates people who reason about state from people who pattern-match on "grid DP".

Order: Unique Paths II → Bomb Enemy → Minimum Falling Path Sum II → Cherry Pickup II → Interleaving String.