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.

flowchart TD A["dp[r][c] = answer for reaching (r, c)"] --> B["compose from the allowed predecessors"] B --> C["Unique Paths II: dp[r-1][c] + dp[r][c-1]
obstacle → 0"] B --> D["Falling Path II: min over the row above,
EXCLUDING the same column"] B --> E["Cherry Pickup II: two agents
state = (row, col1, col2)"] B --> F["Interleaving String: 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

A cell's answer composes from its legal predecessors. Identify them and the recurrence is written.
Obstacles are zeros, not special cases.
Keep the best two when one predecessor may be forbidden.
Simultaneous movers share one state. Independent passes miss the interaction.
Grids appear where no grid is mentioned — two strings are two axes.
Roll to one row for O(n) space, and watch the iteration direction when you do.
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.

Interleaving String

Core idea: Building s3 by shuffling s1 and s2 together means that at every step you grab the next character from either s1 or s2, never reordering within a string. So the only state that matters is how far you've consumed each one: (i, j) = "used the first i chars of s1 and the first j chars of s2." Those i + j characters must spell exactly s3[:i+j]. From a reachable (i, j) you can step to (i+1, j) iff s1[i] == s3[i+j], or to (i, j+1) iff s2[j] == s3[i+j]. Mark dp[i][j] = True when (i, j) is reachable; the answer is dp[m][n]. (And before any of this: if len(s1) + len(s2) != len(s3) it's hopeless — return False immediately.)

The problem, rephrased

You're handed three strings s1, s2, and s3. Return True if s3 can be formed by interleaving s1 and s2 — that is, by merging them into one string while keeping the relative order of characters within each original string. You may alternate between the two freely, but you can never rearrange a string's own characters.

Picture two conveyor belts, one feeding out s1 left-to-right and the other feeding out s2 left-to-right. A robot must produce s3 by repeatedly picking the front item off one belt. The question: is there some sequence of picks that yields exactly s3?

The hard constraint hiding in plain sight: the total length must match. If len(s1) + len(s2) != len(s3), no interleaving can possibly work — every character of s3 has to come from one belt or the other, with none left over and none invented.

A worked input/output

s1	s2	s3	Output	Why
`"aabcc"`	`"dbbca"`	`"aadbbcbcac"`	True	One split: `aa`+`bc`+`c` from s1, `dbbc`+`a` from s2 → `aa dbbc bc a c`.
`"aabcc"`	`"dbbca"`	`"aadbbbaccc"`	False	No alternation reproduces that third `b` then `accc` tail.
`"aab"`	`"abc"`	`"aabbac"`	False	Right length (3+3=6) but no valid merge exists.
`""`	`""`	`""`	True	Two empty belts produce the empty string.
`"abc"`	`"def"`	`"abcde"`	False	Lengths don't add up (3+3 ≠ 5) — instant reject.

Notice the answer depends only on the prefix lengths consumed, never on which concrete split produced them — that's exactly what makes it a 2D table.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Intermediate