Grid & Path DP
A robot stands in the top-left corner of a board. It may only step right or down. How many different routes reach the bottom-right corner? Which route collects the fewest coins of toll? How much health does a knight need to survive the trip? Where is the biggest solid square of land? Can two robots, walking together, pick up more cherries than one robot walking twice?
All of these are grid DP problems: the table you fill is literally the grid, each cell's answer is built from one, two or three neighbouring cells, and the only real decisions are what one cell means and in which order to fill the cells. Grid DP is usually the first place where a learner sees a 2-D DP table, and it is the cleanest one: you can draw it, colour it and watch it fill. Once it clicks, the same picture carries you into Sequence DP (LCS and edit distance are grid DPs over two strings), Interval DP and beyond.
This lesson assumes you have read DP Foundations (state, transition, base case, memoization vs tabulation) and are comfortable indexing a 2-D array, as in Matrices & Grids.
Why this exists
Grids are everywhere: maps, images, game boards, spreadsheets, and every table where one axis is "position in string A" and the other is "position in string B". When movement is restricted so that you can never come back to a cell you have left (right/down only, or "always move to the next row"), the grid becomes a directed acyclic graph (a DAG: arrows that never form a loop). On a DAG, "best route to here" depends only on "best route to the cells just before here", and those were already computed. That is the whole reason DP works on grids, and it is also the reason it stops working the moment the robot can move left or up: then you need BFS or Dijkstra instead.
The counting version is ancient: the number of right/down lattice paths is a binomial coefficient, known since Pascal's triangle (which is itself a grid DP turned 45 degrees). The optimisation version underlies the 1970 Needleman–Wunsch algorithm for aligning DNA, dynamic time warping in speech recognition, and the 2007 seam carving algorithm (Avidan and Shamir) that resizes images by removing the cheapest top-to-bottom path of pixels.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "can only move right or down" (or "down / down-left / down-right") | Grid DP in row-major order |
| "number of unique paths", "how many ways to reach" | Counting DP: ways[r][c] = ways[r-1][c] + ways[r][c-1] |
| "obstacles", "blocked cells", "rocks" | Same counting DP, with blocked cells forced to 0 |
| "minimum sum / cost path", "maximum gold collected" on a one-way grid | Optimisation DP: min or max of the incoming neighbours plus this cell |
| "minimum initial health / fuel / money so that you never drop below 1" | Fill backwards from the goal (dungeon game) |
| "largest square of 1s", "count square submatrices" | side[r][c] = 1 + min(up, left, diag) |
| "largest rectangle of 1s" | Row-by-row histogram + monotonic stack |
| "go there and come back", "two robots / two people walk at once" | Two walkers moving in lockstep, state (step, row1, row2) |
| "triangle", "falling path", "each step goes to the next row" | Row-by-row DP, often bottom-up |
| "path sum divisible by k", "exactly k of something on the path" | Add a dimension: dp[r][c][remainder] |
| Moves in all four directions | Not a DAG: BFS (unit cost) or Dijkstra (weights) — or memoised DFS if values strictly increase along moves |
| Huge grid, very few obstacles | Combinatorics + inclusion–exclusion over obstacles (see Variations) |
The meta-trigger: every move takes you strictly "forward" (to a later row, or a later column, or a later anti-diagonal). Then there is an order in which every cell's predecessors are finished before the cell itself — and that order is your loop.
Intuition & first principles
The "last step" question
Think about any cell in the middle of the board, say row 2, column 3. The robot is standing on it. Where was it one step ago? It moves only right or down, so it was either directly above (row 1, column 3) or directly to the left (row 2, column 2). There is no third option.
That single observation is the whole technique:
- Counting: every route to (2,3) is a route to (1,3) followed by "down", or a route to (2,2) followed by "right". These two groups never overlap (the last move differs), so
ways(2,3) = ways(1,3) + ways(2,2). - Cheapest route: the cheapest route to (2,3) is the cheapest route to one of those two cells, plus the toll of (2,3). So
cost(2,3) = min(cost(1,3), cost(2,2)) + toll(2,3).
An everyday picture: you are walking through a city laid out in blocks, and you only ever walk east or south. Standing at a street corner, you don't need to remember your whole walk to know your best total so far — you only need to know the best totals at the corner north of you and the corner west of you. Each corner hands its number to the next corners, like a bucket brigade.
A tiny example you can hold in your head
Take an empty grid with 3 rows and 4 columns. Write the number of routes into each cell.
- The top row: the robot can only have come from the left, all the way. One route each:
1 1 1 1. - The left column: only from above. One route each.
- Every other cell: add the number above and the number to the left.
row 0: 1 1 1 1
row 1: 1 2 3 4
row 2: 1 3 6 10
Cell (1,1) = 1 + 1 = 2 (down-then-right, or right-then-down). Cell (2,3) = 4 + 6 = 10. There are 10 routes.
Check it another way: every route makes exactly 2 down-moves and 3 right-moves, in some order. Choosing which 2 of the 5 moves are "down" gives . The DP and the formula agree — and the DP keeps working when we add rocks, tolls and monsters, where the formula does not.
Which cells does a cell read?
graph LR
UP["(r-1, c) above"] -->|"down"| CUR["(r, c) being filled"]
LEFT["(r, c-1) left"] -->|"right"| CUR
CUR -->|"down"| BELOW["(r+1, c)"]
CUR -->|"right"| RIGHT["(r, c+1)"]
Arrows go from a cell to the cells it feeds. A cell can be filled as soon as both of its incoming arrows come from filled cells. Going row by row, left to right inside a row (called row-major order), guarantees exactly that.
Why plain recursion is too slow
Write the cheapest-route rule as a recursive function f(r, c) and call f(2, 2). It calls f(1, 2) and f(2, 1). Both of those call f(1, 1). The same question gets asked again and again:
graph TD
A["f(2,2)"] --> B["f(1,2)"]
A --> C["f(2,1)"]
B --> D["f(0,2)"]
B --> E["f(1,1)"]
C --> F["f(1,1)"]
C --> G["f(2,0)"]
E --> H["f(0,1)"]
E --> I["f(1,0)"]
F --> J["f(0,1)"]
F --> K["f(1,0)"]
style E fill:#f96
style F fill:#f96
The number of calls grows like the number of routes, which is — for a 20×20 grid that is 35,345,263,800. But there are only distinct questions. Store each answer the first time you compute it (memoization), or fill them in a safe order (tabulation), and the work drops to 400 small steps. That is DP in one sentence.
The four questions for every grid DP
Before writing any code, answer these on paper:
- What does one cell mean? ("number of routes from the start to here", "cheapest cost to reach here", "health needed when entering here", "side of the biggest square whose bottom-right corner is here").
- Which cells does it read? (above and left; or below and right; or above, left and the diagonal).
- What are the edges? (first row, first column, blocked cells, out-of-grid neighbours).
- In which order must the cells be filled so that every read cell is already done?
The rest of the lesson answers these four questions for five classic problems.
Mechanics
1. Unique paths (counting on an empty grid)
State: ways[r][c] = number of right/down routes from (0,0) to (r,c).
Transition: ways[r][c] = ways[r-1][c] + ways[r][c-1].
Base: ways[0][c] = ways[r][0] = 1.
Order: row-major.
Answer: ways[R-1][C-1].
Dry run on the 3×4 grid. Each row of the trace table fills one cell and says which cells it reads.
| Step | Cell | Reads | Computation | Value |
|---|---|---|---|---|
| 1–4 | (0,0)…(0,3) | — (top row) | base case | 1, 1, 1, 1 |
| 5 | (1,0) | — (left column) | base case | 1 |
| 6 | (1,1) | (0,1)=1, (1,0)=1 | 1 + 1 | 2 |
| 7 | (1,2) | (0,2)=1, (1,1)=2 | 1 + 2 | 3 |
| 8 | (1,3) | (0,3)=1, (1,2)=3 | 1 + 3 | 4 |
| 9 | (2,0) | — (left column) | base case | 1 |
| 10 | (2,1) | (1,1)=2, (2,0)=1 | 2 + 1 | 3 |
| 11 | (2,2) | (1,2)=3, (2,1)=3 | 3 + 3 | 6 |
| 12 | (2,3) | (1,3)=4, (2,2)=6 | 4 + 6 | 10 |
One row is enough. Look at what step 7 reads: the cell above (from the previous row) and the cell to its left (just written in this row). If we keep a single array dp of length C, then before we update dp[c] it still holds the value from the row above, and dp[c-1] already holds the new value for this row. So dp[c] += dp[c-1] does the whole transition in place. Memory drops from to .
Deeper: the closed form and Pascal's triangle
Every route is a word of letters D and letters R, so the count is . Rotate the table 45° and you get Pascal's triangle: the DP rule ways = above + left is exactly Pascal's rule . The closed form takes multiplications, but the numbers become big very quickly (for a 100×100 grid they have 59 digits), so problems that ask for counts "modulo " usually want either the DP or factorials with modular inverses (see Counting DP).
2. Unique paths with obstacles
Now some cells are rocks (marked 1). A route may not touch a rock.
The only change: a rock cell has 0 routes. It contributes nothing to its neighbours, so routes "flow around" it automatically. The first row and column are no longer all 1s: once a rock appears in the top row, every cell to its right in that row has 0 routes, because the only way in was through the rock.
Example (# = rock):
. . . .
. # . .
. . . #
# . . .
Row-by-row, with the single rolling array dp:
| After row | Row contents | dp | Notes |
|---|---|---|---|
| start | — | [1, 0, 0, 0] | dp[0] = 1 because the start is open |
| 0 | . . . . | [1, 1, 1, 1] | each cell adds the left neighbour |
| 1 | . # . . | [1, 0, 1, 2] | rock at column 1 → 0; column 2 = 1 (above) + 0 (rock) |
| 2 | . . . # | [1, 1, 2, 0] | column 3 is a rock → 0 |
| 3 | # . . . | [0, 1, 3, 3] | column 0 is a rock → 0; column 3 = 0 (above, rock) + 3 |
Answer: 3 routes. Writing D for down and R for right, they are DDRDRR, DDRRDR and RRDDDR: each avoids the rocks at (1,1), (2,3) and (3,0). The test code also checks the table against a brute-force enumeration of all 20 right/down routes of a 4×4 grid.
Two edge cases deserve a sentence each:
- If the start is a rock, the answer is 0 (
dp[0]starts at 0). - If the goal is a rock, the answer is 0 (the last cell is forced to 0).
3. Minimum path sum (optimisation, plus getting the path back)
Each cell now has a toll. Find the right/down route with the smallest total toll, counting both the start and the goal cell.
cost: 3 1 4 2
2 7 1 8
5 3 2 1
State: dp[r][c] = smallest total toll of any route from (0,0) to (r,c), including both ends.
Transition: dp[r][c] = min(dp[r-1][c], dp[r][c-1]) + cost[r][c].
Base: dp[0][0] = cost[0][0]; top row and left column have only one incoming neighbour.
Order: row-major.
The whiteboard version: the top row is a running sum, 3, 4, 8, 10. The left column too: 3, 5, 10. Then cell (1,1): coming from above costs 4, from the left 5, take 4, add 7 → 11. Cell (1,2): above is 8, left is 11, take 8, add 1 → 9. And so on.
| Step | Cell | Reads (up, left) | Computation | dp |
|---|---|---|---|---|
| 1 | (0,0) | — | start: cost 3 | 3 |
| 2 | (0,1) | left 3 | 3 + 1 | 4 |
| 3 | (0,2) | left 4 | 4 + 4 | 8 |
| 4 | (0,3) | left 8 | 8 + 2 | 10 |
| 5 | (1,0) | up 3 | 3 + 2 | 5 |
| 6 | (1,1) | up 4, left 5 | min(4, 5) + 7 | 11 |
| 7 | (1,2) | up 8, left 11 | min(8, 11) + 1 | 9 |
| 8 | (1,3) | up 10, left 9 | min(10, 9) + 8 | 17 |
| 9 | (2,0) | up 5 | 5 + 5 | 10 |
| 10 | (2,1) | up 11, left 10 | min(11, 10) + 3 | 13 |
| 11 | (2,2) | up 9, left 13 | min(9, 13) + 2 | 11 |
| 12 | (2,3) | up 17, left 11 | min(17, 11) + 1 | 12 |
The finished table:
dp: 3 4 8 10
5 11 9 17
10 13 11 12
Getting the route back (reconstruction). The table stores totals, not routes. To recover a best route, start at the goal and repeatedly ask "which neighbour did my value come from?" — the one with the smaller dp value. From (2,3) = 12: up is 17, left is 11 → go left to (2,2). From 11: up 9, left 13 → up to (1,2). From 9: up 8, left 11 → up to (0,2). Then left, left. Reverse the walk:
(0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (2,3), tolls 3 + 1 + 4 + 1 + 2 + 1 = 12. ✔
Step through it. The cell being filled is amber (active); the cells it reads are cyan (frontier). The last frame draws the recovered route.
Reconstruction needs the full table
The rolling-array trick (keep only one row) still gives the right total, but it throws away the information needed to walk back. If you need the route, keep the whole table, or store one "came from up / came from left" bit per cell ( bits instead of integers).
The fill order, made visible
The order of the loops is not a detail; it is a correctness requirement. The rule is: when you fill a cell, every cell it reads must already be final. Different problems read different neighbours, so they need different orders.
| Problem | Cell reads | Valid fill orders |
|---|---|---|
| Unique paths, min path sum | up, left | row-major (rows top→bottom, columns left→right); column-major also works; anti-diagonals by increasing r + c also work |
| Maximal square | up, left, up-left | row-major or column-major |
| Dungeon game | down, right | reverse row-major (rows bottom→top, columns right→left) |
| Cherry pickup | previous anti-diagonal | anti-diagonals by increasing step t = r + c |
| Falling path / triangle | the row above (or below) | row by row; inside a row any order |
graph LR
subgraph forward["Forward fill: reads up and left"]
F1["(0,0)"] --> F2["(0,1)"] --> F3["(0,2)"]
F4["(1,0)"] --> F5["(1,1)"] --> F6["(1,2)"]
F1 --> F4
F2 --> F5
F3 --> F6
end
subgraph backward["Backward fill: reads down and right"]
B6["(1,2) goal side"] --> B5["(1,1)"] --> B4["(1,0)"]
B3["(0,2)"] --> B2["(0,1)"] --> B1["(0,0) answer"]
B6 --> B3
B5 --> B2
B4 --> B1
end
The arrows show "is needed by". In a forward problem the answer sits at the bottom-right and the base case at the top-left. In a backward problem it is the other way round.
4. Dungeon game: why we fill backwards
The setup: a knight starts at the top-left room and must reach the princess at the bottom-right, moving right or down. Each room either hurts him (a negative number: a demon) or heals him (a positive number: a potion). His health must stay at least 1 at every moment, including after the last room. What is the smallest starting health that works for some route?
rooms: -3 5 -10
-6 -2 4
2 -8 -1
First attempt: go forwards, and see it break
A natural idea is to fill the table forwards like min path sum: at each cell keep "the smallest starting health needed to get here". The trouble is that the cell needs two facts about the route that reached it:
- how deep the health ever dipped (this decides the starting health), and
- how much health is left right now (this decides how the future goes).
These two facts can pull in opposite directions, and a single number cannot keep both. Here is a concrete failure. Grid:
1 -3 3
0 -2 0
-3 -3 -3
Look at cell (1,2), just above the goal. Two routes reach it:
- From above, via 1, −3, 3, 0: running total ends at +1, deepest dip −2, so it needs starting health 3.
- From the left, via 1, 0, −2, 0: running total ends at −1, deepest dip −1, so it needs starting health 2.
A forward rule that keeps "smallest starting health so far" keeps the second route (2 < 3). Then the last room (−3) arrives. The kept route drops to −4 and now needs starting health 5. The discarded route would have dropped only to −2 and needed 3. The forward DP answers 5; the true answer is 3. It threw away the better route because, at (1,2), neither route was better on both facts. (The test file for this lesson runs this exact forward rule and confirms it answers 5.)
When a cell's "best so far" cannot be summed up in one comparable number, forward DP has no optimal substructure: the best way to reach the middle is not necessarily part of the best overall route.
Second attempt: ask the question from the end
Turn the question around. Instead of "what do I need to get here from the start?", ask "if I am about to enter this room, how much health do I need to finish from here?" Call that need[r][c].
Now one number is enough, because the future from (r,c) does not care how you got to (r,c) — only how much health you bring. And more health is never worse. So:
- After the princess's room you need at least 1. Pretend there are two "virtual" cells past the goal with
need = 1. - Entering room (r,c), you will next enter either the room below or the room to the right, and you pick whichever needs less:
next = min(need[r+1][c], need[r][c+1]). - Room (r,c) changes your health by
rooms[r][c], so you must enter it withnext - rooms[r][c]. But you can never enter with less than 1 (you'd already be dead), so:
This reads down and right, so we fill from the bottom-right corner, row by row upwards, right to left inside each row.
Dry run on the first grid:
| Step | Cell | Room | Reads (down, right) | next | need = max(1, next − room) |
|---|---|---|---|---|---|
| 1 | (2,2) | −1 | virtual 1, virtual 1 | 1 | max(1, 1 + 1) = 2 |
| 2 | (2,1) | −8 | —, (2,2)=2 | 2 | max(1, 2 + 8) = 10 |
| 3 | (2,0) | 2 | —, (2,1)=10 | 10 | max(1, 10 − 2) = 8 |
| 4 | (1,2) | 4 | (2,2)=2, — | 2 | max(1, 2 − 4) = 1 |
| 5 | (1,1) | −2 | (2,1)=10, (1,2)=1 | 1 | max(1, 1 + 2) = 3 |
| 6 | (1,0) | −6 | (2,0)=8, (1,1)=3 | 3 | max(1, 3 + 6) = 9 |
| 7 | (0,2) | −10 | (1,2)=1, — | 1 | max(1, 1 + 10) = 11 |
| 8 | (0,1) | 5 | (1,1)=3, (0,2)=11 | 3 | max(1, 3 − 5) = 1 |
| 9 | (0,0) | −3 | (1,0)=9, (0,1)=1 | 1 | max(1, 1 + 3) = 4 |
need: 4 1 11
9 3 1
8 10 2
The answer is need[0][0] = 4. Follow the smaller need forwards to see the route: right to (0,1), down to (1,1), right to (1,2), down to (2,2). Health: start 4 → 1 → 6 → 4 → 8 → 7. It touches 1 once and never drops below. Start with 3 and the first demon leaves 0 — dead.
Step 4 shows why the max(1, …) matters: room (1,2) is a +4 potion and the room after needs 2, so "2 − 4 = −2" would say "enter with −2 health", which is meaningless. You must be alive to enter, so the floor is 1.
The general lesson: fill from the side where the state is simple
If the quantity you want depends on what happens later ("enough to survive the rest"), define the state as "from here to the end" and fill from the end. If it depends on what happened earlier ("cheapest so far"), define it as "from the start to here". The dungeon is the classic case where only the backward state is a single number.
Deeper: binary search on the answer also works
"Can the knight survive with starting health ?" is monotone in : if works, works. For a fixed , a forward DP that keeps the maximum health remaining at each cell (or if dead) is correct, because with a fixed start, "more health now" really does dominate. Binary search over gives . It is slower than the backward DP but is a useful trick when the backward formulation is not obvious — the same "guess the answer, then check" move appears in Partition DP.
5. Maximal square
Given a 0/1 matrix, find the area of the largest square made only of 1s.
1 0 1 1 1
1 1 1 1 1
0 1 1 1 1
1 1 1 1 0
State: side[r][c] = side length of the largest all-1 square whose bottom-right corner is (r,c). (Pinning one corner is what makes the state small: every square has exactly one bottom-right corner.)
Transition: if the cell is 0, side = 0. Otherwise
Why the minimum of three? A square of side ending at (r,c) contains three squares of side : one ending just above, one ending just to the left, and one ending at the diagonal. All three must exist. Conversely, if all three squares of side exist and (r,c) is a 1, they cover the whole block except (r,c) itself. So the biggest is limited by the weakest of the three neighbours.
graph TD
D["diag (r-1,c-1): side 2"] --> X["(r,c) = 1 + min(2, 2, 1) = 2"]
U["up (r-1,c): side 2"] --> X
L["left (r,c-1): side 1"] --> X
Filled table (computed by the generator, row-major):
side: 1 0 1 1 1
1 1 1 2 2
0 1 2 2 3
1 1 2 3 0
Selected steps of the dry run:
| Cell | Matrix | up, left, diag | side | best so far |
|---|---|---|---|---|
| (1,1) | 1 | 0, 1, 1 | 1 + 0 = 1 | 1 |
| (1,3) | 1 | 1, 1, 1 | 1 + 1 = 2 | 2 |
| (1,4) | 1 | 1, 2, 1 | 1 + 1 = 2 | 2 |
| (2,2) | 1 | 1, 1, 1 | 2 | 2 |
| (2,3) | 1 | 2, 2, 1 | 2 | 2 |
| (2,4) | 1 | 2, 2, 2 | 1 + 2 = 3 | 3 |
| (3,3) | 1 | 2, 2, 2 | 3 | 3 |
| (3,4) | 0 | — | 0 | 3 |
The best side is 3, so the area is 9: rows 0–2, columns 2–4. (There is a second 3×3 square ending at (3,3); the DP finds both.)
A small change gives a different problem for free: sum all the side values instead of taking the maximum, and you have counted every all-1 square submatrix. A corner with side 3 is the bottom-right corner of exactly three squares (sides 1, 2 and 3).
Deeper: why not rectangles?
For the largest all-1 rectangle, the "min of three" trick fails: a rectangle is described by two numbers (height, width), and different neighbours may favour tall-thin or short-wide shapes — the same "two facts that conflict" problem as the forward dungeon. The standard fix is to treat each row as the floor of a histogram (height[c] = consecutive 1s ending at this row) and run the "largest rectangle in a histogram" monotonic stack on each row: total.
6. Cherry pickup: two walkers and a 3-D state
An field has cherries (1), empty cells (0) and thorns (−1, impassable). You walk from top-left to bottom-right moving right/down, picking every cherry you pass, then walk back moving left/up, picking again. A cherry can only be picked once. Maximise the total. If no route exists, the answer is 0.
Why "best path, then best path again" is wrong
The tempting plan: find the best single route, pick its cherries, then find the best route on what is left. Here is a field where that loses a cherry:
1 1 1 0
0 0 1 1
1 1 1 0
1 0 1 1
The best single route takes 7 cherries: across the top two cells, down the third column, then right along the bottom: (0,0) (0,1) (0,2) (1,2) (2,2) (3,2) (3,3). After that, the cherries left are at (1,3), (2,0), (2,1), (3,0), and no single right/down route can grab more than 2 of them. Greedy total: 9.
The best pair of routes takes 10: one route goes along the top and down the right side, (0,0) (0,1) (0,2) (1,2) (1,3) (2,3) (3,3) for 6; the other goes down the left and along row 2, (0,0) (1,0) (2,0) (2,1) (2,2) (3,2) (3,3) for 4 new cherries. Neither of these is the greedy "best single route", so greedy can never find them. The two trips must be planned together.
Step 1: the return trip is just another forward trip
A left/up route from the goal back to the start, read backwards, is a right/down route from the start to the goal. So the problem is: choose two right/down routes from (0,0) to (n−1, n−1) maximising the cherries on their union.
Step 2: walk them at the same time
Send two walkers, A and B, at the same moment, each taking one step per tick. After ticks, a walker at (r, c) has made down-moves and right-moves, so . Both walkers are always on the same anti-diagonal. Two great consequences:
- The state shrinks. Knowing , and tells you both positions: , . The state is — three numbers, a 3-D table.
- Double counting becomes easy. A cell on anti-diagonal can only ever be visited at tick . So if the two walkers ever share a cell, they share it at the same tick, which means right now. Count the cherry once in that case, twice-distinct otherwise. No need to remember the past.
Step 3: the transition
Each walker came from either above or the left, so there are predecessor states:
graph LR
P1["t-1: (r1-1, r2-1) both moved down"] --> S["t: (r1, r2)"]
P2["t-1: (r1-1, r2) A down, B right"] --> S
P3["t-1: (r1, r2-1) A right, B down"] --> S
P4["t-1: (r1, r2) both moved right"] --> S
where is the grid value, any state on a thorn is impossible (), and is 1 if the walkers are on different cells, else 0. Base: . Answer: .
Two savings: tick only reads tick , so keep two layers (space ). And the walkers are interchangeable, so we may insist and fill half of each layer.
Dry run, layer by layer
Field (thorns marked −1):
0 1 1 -1
1 0 -1 1
1 1 0 1
-1 1 1 0
Each line lists the reachable states at tick as (A's cell, B's cell) → cherries so far (computed by the test script, with ):
| Tick t | Reachable states → value | What happened |
|---|---|---|
| 0 | (0,0),(0,0) → 0 | both start on an empty cell |
| 1 | (0,1),(0,1) → 1 · (0,1),(1,0) → 2 · (1,0),(1,0) → 1 | splitting up picks both cherries |
| 2 | (0,2),(0,2) → 2 · (0,2),(1,1) → 3 · (0,2),(2,0) → 4 · (1,1),(1,1) → 2 · (1,1),(2,0) → 3 · (2,0),(2,0) → 2 | best: one along the top, one down the left |
| 3 | (2,1),(2,1) → 4 | thorns at (0,3), (1,2), (3,0) leave a single open cell on this diagonal: both walkers must squeeze through (2,1) |
| 4 | (2,2),(2,2) → 4 · (2,2),(3,1) → 5 · (3,1),(3,1) → 5 | |
| 5 | (2,3),(2,3) → 5 · (2,3),(3,2) → 7 · (3,2),(3,2) → 6 | split again: both cherries |
| 6 | (3,3),(3,3) → 7 | answer 7 |
Notice tick 3: both walkers stand on (2,1) and its cherry is counted once (value stays 4). That is the rule doing its job. The cherry at (1,3) is never collected: the only ways into (1,3) are from (0,3) and (1,2), and both are thorns. Nobody has to tell the DP this; no reachable state ever contains (1,3).
Deeper: why the 3-D state is enough (and a 4-D one is not needed)
A naive state is : four numbers, states. Synchronising by removes one dimension because ; symmetry halves what is left. The deeper reason it is correct — not just smaller — is the anti-diagonal argument: overlap can only happen at equal ticks, so "has this cherry been taken?" never needs history. Without synchronisation (say, walker A goes first, then B), you would need to remember A's whole route, which is exponentially many possibilities. "Move the two agents in lockstep so their interaction is local in time" is a reusable trick; Cherry Pickup II (two robots moving down rows) uses the same idea with = row number.
The ladder: brute force → better → optimal
Problem: minimum path sum on an grid, right/down moves.
Rung 1: try every route
Every route is a choice of which of the moves go down. Enumerate them all, add up each route's tolls, keep the smallest.
from itertools import combinations
def min_path_sum_brute(cost):
R, C = len(cost), len(cost[0])
best = None
for downs in combinations(range(R + C - 2), R - 1): # which of the moves go down
r = c = 0
total = cost[0][0]
for step in range(R + C - 2):
if step in downs:
r += 1
else:
c += 1
total += cost[r][c]
best = total if best is None else min(best, total)
return best
Time — exponential. On a 15×15 grid that is about 40 million routes. Useful only as a test oracle for tiny grids (which is how this lesson's code was checked).
Rung 2: recursion with memoization (top-down)
Ask "cheapest way to reach (r,c)?" recursively, and remember answers.
from functools import lru_cache
def min_path_sum_memo(cost):
@lru_cache(maxsize=None)
def f(r, c): # cheapest way to reach (r, c) from (0, 0)
if r == 0 and c == 0:
return cost[0][0]
best = float("inf")
if r > 0:
best = min(best, f(r - 1, c))
if c > 0:
best = min(best, f(r, c - 1))
return best + cost[r][c]
return f(len(cost) - 1, len(cost[0]) - 1)
Each of the cells is computed once with work: time, memo. But the recursion depth reaches , which overflows Python's default stack around a 500×500 grid, and function-call overhead is large.
Rung 3: tabulation (bottom-up)
Fill the table in row-major order with two loops (the code in Implementation). Same time, space, no recursion, cache-friendly, and the table is there for path reconstruction.
Rung 4: one rolling row
Keep only the current row: time, space (loop over the longer side, keep an array for the shorter). Use it when you only need the total.
Side rung: Dijkstra
If you didn't notice the grid is a DAG, Dijkstra on the grid graph also works (tolls are non-negative): . It is the right tool when moves go in all four directions; for right/down moves it is a heavier hammer than needed.
| Rung | Method | Time | Extra space | Why it is better than the rung above |
|---|---|---|---|---|
| 1 | Enumerate all routes | Baseline; obviously correct | ||
| 2 | Memoized recursion | + stack | Each cell solved once instead of once per route through it | |
| 3 | Tabulation | No recursion, no stack overflow, keeps the table for reconstruction | ||
| 4 | Rolling row | Same speed, memory of one row | ||
| side | Dijkstra | Handles 4-direction moves; overkill here |
The same ladder applies to every problem in this lesson. For cherry pickup the brute force is "all pairs of routes" (), the naive DP is 4-D (), and the synchronised DP is time and space.
Correctness
All five proofs follow one template: induction over the fill order. Claim: when a cell is filled, its value is correct. The base cells are correct by direct argument. For any other cell, the cells it reads were filled earlier (that is what the fill order guarantees), so by induction they are correct, and the transition turns correct inputs into a correct output.
Unique paths. Split the routes to (r,c) by their last move. Those ending with "down" are in one-to-one correspondence with routes to (r−1,c); those ending with "right" with routes to (r,c−1). The two groups are disjoint (different last move) and cover everything (there is no third move), so the sum is exact. With rocks: a route through a rock is forbidden, so the rock's count is 0, and every other cell's argument is unchanged.
Minimum path sum (optimal substructure). Let be a cheapest route to (r,c) and suppose its last move came from (r−1,c). The part of before the last cell is a route to (r−1,c). If there were a cheaper route to (r−1,c), swapping it in would give a cheaper route to (r,c) — contradiction. So 's cost is dp[r-1][c] + cost[r][c], which is one of the two options the min considers; and both options are achievable routes, so the min is exactly the optimum. (This "cut and paste" argument is the standard optimal-substructure proof from CLRS §14.3.)
Dungeon game. Define = minimum health on entering (r,c) that lets you finish. Two facts:
- Monotonicity: if health lets you finish from (r,c), so does any (follow the same route; you are always healthier).
- One-step decomposition: entering with , you leave with , and that must be at least of the next room you choose. You choose the cheaper next room.
So works iff and , and the smallest such is exactly the formula. Because the next room's requirement already includes "stay ", the intermediate check is implied. The virtual cells with encode "after the princess's room you must be alive". Forward DP fails because fact 1 does not hold for the forward state "minimum start needed so far" — two routes to the same cell are not comparable, as the counterexample showed.
Maximal square. Claim: an all-1 square of side with bottom-right corner (r,c) exists iff (r,c) is 1 and all-1 squares of side end at (r−1,c), (r,c−1) and (r−1,c−1). "Only if": the three sub-squares are inside the big one. "If": the union of the three -squares covers every cell of the block except (r,c), which is 1. Since a square of side ending at a cell implies squares of every smaller side end there too, the largest is of the three neighbours' values.
Cherry pickup. (1) Reversing the return route gives a bijection between round trips and ordered pairs of forward routes, with the same set of visited cells. (2) Pairs of forward routes correspond one-to-one to sequences of states , , each step one of the four moves. (3) The cherries collected by a pair equal the sum over of the cherries on the cells occupied at tick , counting a cell once if both walkers are on it — because a cell on anti-diagonal can only be occupied at tick , so no cell is counted at two different ticks. Hence the value of a state sequence is a sum of per-tick terms that depend only on the current state, which is exactly the shape a max-plus DP over ticks optimises. The symmetry is valid because swapping the walkers' labels changes nothing.
Complexity
| Problem | Time | Space (table) | Space (rolling) | Why |
|---|---|---|---|---|
| Unique paths | cells, work each | |||
| Unique paths (closed form) | big-number ops | — | ||
| With obstacles | as above | |||
| Min path sum | table needed for reconstruction | |||
| Dungeon game | one backward pass | |||
| Maximal square | (+1 variable for the diagonal) | 3 reads per cell | ||
| Cherry pickup | ticks × pairs × 4 predecessors |
Every one of these is optimal in the sense that any correct algorithm must at least read all cells (a single changed toll anywhere can change the answer), except cherry pickup, where is the best known for this formulation.
Integer sizes. Path counts overflow signed 32-bit integers from an 18×18 grid () and signed 64-bit integers from a 35×35 grid (). Use 64-bit, big integers, or the modulus the problem gives. Dungeon need values can be up to (number of cells on a route) × (largest demon) + 1; with 200×200 rooms of −1000 that is about 400,000, fine in 32 bits.
Implementation
The first group has the counting and min-path problems (with path reconstruction); the second has the dungeon game, maximal square and cherry pickup. Each block is complete and runs its own tests on the examples from this lesson. They were also checked against brute force on 400 random small grids.
Paths: counting, obstacles, min path sum
from math import comb
from typing import List, Tuple
def unique_paths(rows: int, cols: int) -> int:
"""Right/down paths in an empty rows x cols grid, one rolling row."""
dp = [1] * cols # top row: one way to reach each cell
for _ in range(1, rows):
for c in range(1, cols):
dp[c] += dp[c - 1] # dp[c] (from above) + dp[c-1] (from the left)
return dp[-1]
def unique_paths_with_obstacles(grid: List[List[int]]) -> int:
"""grid[r][c] == 1 is a rock. Count right/down paths from top-left to bottom-right."""
cols = len(grid[0])
dp = [0] * cols
dp[0] = 1 if grid[0][0] == 0 else 0
for row in grid:
for c in range(cols):
if row[c] == 1:
dp[c] = 0 # no path goes through a rock
elif c > 0:
dp[c] += dp[c - 1]
return dp[-1]
def min_path_sum(cost: List[List[int]]) -> Tuple[int, List[Tuple[int, int]]]:
"""Cheapest right/down path; returns (total, list of cells on one best path)."""
R, C = len(cost), len(cost[0])
dp = [[0] * C for _ in range(R)]
for r in range(R):
for c in range(C):
if r == 0 and c == 0:
dp[r][c] = cost[0][0]
elif r == 0:
dp[r][c] = dp[r][c - 1] + cost[r][c]
elif c == 0:
dp[r][c] = dp[r - 1][c] + cost[r][c]
else:
dp[r][c] = min(dp[r - 1][c], dp[r][c - 1]) + cost[r][c]
path, r, c = [(R - 1, C - 1)], R - 1, C - 1
while (r, c) != (0, 0): # walk back to whichever neighbour produced dp[r][c]
if r == 0 or (c > 0 and dp[r][c - 1] <= dp[r - 1][c]):
c -= 1
else:
r -= 1
path.append((r, c))
path.reverse()
return dp[R - 1][C - 1], path
if __name__ == "__main__":
assert unique_paths(3, 4) == 10 == comb(5, 2)
assert unique_paths(1, 1) == 1
assert unique_paths(10, 10) == comb(18, 9)
rocks = [[0, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 0, 1],
[1, 0, 0, 0]]
assert unique_paths_with_obstacles(rocks) == 3
assert unique_paths_with_obstacles([[1]]) == 0
assert unique_paths_with_obstacles([[0, 1], [1, 0]]) == 0
cost = [[3, 1, 4, 2],
[2, 7, 1, 8],
[5, 3, 2, 1]]
total, path = min_path_sum(cost)
assert total == 12
assert path == [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3)]
assert sum(cost[r][c] for r, c in path) == total
print("all paths tests passed")
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class GridPaths {
static long uniquePaths(int rows, int cols) {
long[] dp = new long[cols];
java.util.Arrays.fill(dp, 1); // top row
for (int r = 1; r < rows; r++)
for (int c = 1; c < cols; c++)
dp[c] += dp[c - 1]; // from above + from the left
return dp[cols - 1];
}
static long uniquePathsWithObstacles(int[][] grid) {
int cols = grid[0].length;
long[] dp = new long[cols];
dp[0] = grid[0][0] == 0 ? 1 : 0;
for (int[] row : grid)
for (int c = 0; c < cols; c++) {
if (row[c] == 1) dp[c] = 0; // rock: no path through here
else if (c > 0) dp[c] += dp[c - 1];
}
return dp[cols - 1];
}
/** Returns the best total; fills {@code path} with the cells {r, c} of one best path. */
static int minPathSum(int[][] cost, List<int[]> path) {
int R = cost.length, C = cost[0].length;
int[][] dp = new int[R][C];
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++) {
if (r == 0 && c == 0) dp[r][c] = cost[0][0];
else if (r == 0) dp[r][c] = dp[r][c - 1] + cost[r][c];
else if (c == 0) dp[r][c] = dp[r - 1][c] + cost[r][c];
else dp[r][c] = Math.min(dp[r - 1][c], dp[r][c - 1]) + cost[r][c];
}
int r = R - 1, c = C - 1;
path.clear();
path.add(new int[]{r, c});
while (r != 0 || c != 0) {
if (r == 0 || (c > 0 && dp[r][c - 1] <= dp[r - 1][c])) c--;
else r--;
path.add(new int[]{r, c});
}
Collections.reverse(path);
return dp[R - 1][C - 1];
}
public static void main(String[] args) {
check(uniquePaths(3, 4) == 10);
check(uniquePaths(1, 1) == 1);
check(uniquePaths(10, 10) == 48620);
int[][] rocks = {{0, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}};
check(uniquePathsWithObstacles(rocks) == 3);
check(uniquePathsWithObstacles(new int[][]{{1}}) == 0);
check(uniquePathsWithObstacles(new int[][]{{0, 1}, {1, 0}}) == 0);
int[][] cost = {{3, 1, 4, 2}, {2, 7, 1, 8}, {5, 3, 2, 1}};
List<int[]> path = new ArrayList<>();
check(minPathSum(cost, path) == 12);
int[][] want = {{0, 0}, {0, 1}, {0, 2}, {1, 2}, {2, 2}, {2, 3}};
check(path.size() == want.length);
for (int i = 0; i < want.length; i++)
check(path.get(i)[0] == want[i][0] && path.get(i)[1] == want[i][1]);
System.out.println("all paths tests passed");
}
static void check(boolean ok) {
if (!ok) throw new AssertionError("test failed");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
long long uniquePaths(int rows, int cols) {
vector<long long> dp(cols, 1); // top row
for (int r = 1; r < rows; r++)
for (int c = 1; c < cols; c++)
dp[c] += dp[c - 1]; // from above + from the left
return dp[cols - 1];
}
long long uniquePathsWithObstacles(const vector<vector<int>>& grid) {
int cols = grid[0].size();
vector<long long> dp(cols, 0);
dp[0] = grid[0][0] == 0 ? 1 : 0;
for (const auto& row : grid)
for (int c = 0; c < cols; c++) {
if (row[c] == 1) dp[c] = 0; // rock: no path through here
else if (c > 0) dp[c] += dp[c - 1];
}
return dp[cols - 1];
}
// Returns {best total, cells of one best path}.
pair<int, vector<pair<int, int>>> minPathSum(const vector<vector<int>>& cost) {
int R = cost.size(), C = cost[0].size();
vector<vector<int>> dp(R, vector<int>(C));
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++) {
if (r == 0 && c == 0) dp[r][c] = cost[0][0];
else if (r == 0) dp[r][c] = dp[r][c - 1] + cost[r][c];
else if (c == 0) dp[r][c] = dp[r - 1][c] + cost[r][c];
else dp[r][c] = min(dp[r - 1][c], dp[r][c - 1]) + cost[r][c];
}
vector<pair<int, int>> path;
int r = R - 1, c = C - 1;
path.push_back(make_pair(r, c));
while (r != 0 || c != 0) {
if (r == 0 || (c > 0 && dp[r][c - 1] <= dp[r - 1][c])) c--;
else r--;
path.push_back(make_pair(r, c));
}
reverse(path.begin(), path.end());
return make_pair(dp[R - 1][C - 1], path);
}
int main() {
assert(uniquePaths(3, 4) == 10);
assert(uniquePaths(1, 1) == 1);
assert(uniquePaths(10, 10) == 48620);
vector<vector<int>> rocks = {{0, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}};
assert(uniquePathsWithObstacles(rocks) == 3);
assert(uniquePathsWithObstacles({{1}}) == 0);
assert(uniquePathsWithObstacles({{0, 1}, {1, 0}}) == 0);
vector<vector<int>> cost = {{3, 1, 4, 2}, {2, 7, 1, 8}, {5, 3, 2, 1}};
pair<int, vector<pair<int, int>>> res = minPathSum(cost);
assert(res.first == 12);
vector<pair<int, int>> want = {{0, 0}, {0, 1}, {0, 2}, {1, 2}, {2, 2}, {2, 3}};
assert(res.second == want);
cout << "all paths tests passed\n";
return 0;
}
function uniquePaths(rows: number, cols: number): number {
const dp: number[] = new Array(cols).fill(1); // top row
for (let r = 1; r < rows; r++)
for (let c = 1; c < cols; c++) dp[c] += dp[c - 1]; // from above + from the left
return dp[cols - 1];
}
function uniquePathsWithObstacles(grid: number[][]): number {
const cols = grid[0].length;
const dp: number[] = new Array(cols).fill(0);
dp[0] = grid[0][0] === 0 ? 1 : 0;
for (const row of grid)
for (let c = 0; c < cols; c++) {
if (row[c] === 1) dp[c] = 0; // rock: no path through here
else if (c > 0) dp[c] += dp[c - 1];
}
return dp[cols - 1];
}
function minPathSum(cost: number[][]): [number, Array<[number, number]>] {
const R = cost.length, C = cost[0].length;
const dp: number[][] = Array.from({ length: R }, () => new Array<number>(C).fill(0));
for (let r = 0; r < R; r++)
for (let c = 0; c < C; c++) {
if (r === 0 && c === 0) dp[r][c] = cost[0][0];
else if (r === 0) dp[r][c] = dp[r][c - 1] + cost[r][c];
else if (c === 0) dp[r][c] = dp[r - 1][c] + cost[r][c];
else dp[r][c] = Math.min(dp[r - 1][c], dp[r][c - 1]) + cost[r][c];
}
let r = R - 1, c = C - 1;
const path: Array<[number, number]> = [[r, c]];
while (r !== 0 || c !== 0) {
if (r === 0 || (c > 0 && dp[r][c - 1] <= dp[r - 1][c])) c--;
else r--;
path.push([r, c]);
}
path.reverse();
return [dp[R - 1][C - 1], path];
}
function assert(ok: boolean, msg = "test failed"): void {
if (!ok) throw new Error(msg);
}
assert(uniquePaths(3, 4) === 10);
assert(uniquePaths(1, 1) === 1);
assert(uniquePaths(10, 10) === 48620);
const rocks = [[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 0]];
assert(uniquePathsWithObstacles(rocks) === 3);
assert(uniquePathsWithObstacles([[1]]) === 0);
assert(uniquePathsWithObstacles([[0, 1], [1, 0]]) === 0);
const [total, path] = minPathSum([[3, 1, 4, 2], [2, 7, 1, 8], [5, 3, 2, 1]]);
assert(total === 12);
assert(JSON.stringify(path) === JSON.stringify([[0, 0], [0, 1], [0, 2], [1, 2], [2, 2], [2, 3]]));
console.log("all paths tests passed");
The TypeScript number type is a 64-bit float, exact for integers only up to ; path counts from a 30×30 grid on need bigint or a modulus.
Dungeon game, maximal square, cherry pickup
from typing import List
def calculate_minimum_hp(rooms: List[List[int]]) -> int:
"""Smallest starting health so the knight never drops to 0 on some right/down path."""
R, C = len(rooms), len(rooms[0])
INF = float("inf")
need = [[INF] * (C + 1) for _ in range(R + 1)]
need[R][C - 1] = need[R - 1][C] = 1 # after the goal you must still be alive
for r in range(R - 1, -1, -1):
for c in range(C - 1, -1, -1):
nxt = min(need[r + 1][c], need[r][c + 1])
need[r][c] = max(1, nxt - rooms[r][c])
return int(need[0][0])
def maximal_square(m: List[List[int]]) -> int:
"""Area of the largest all-1 square in a 0/1 matrix."""
R, C = len(m), len(m[0])
dp = [[0] * (C + 1) for _ in range(R + 1)] # padded: row 0 and column 0 are zeros
best = 0
for r in range(1, R + 1):
for c in range(1, C + 1):
if m[r - 1][c - 1] == 1:
dp[r][c] = 1 + min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1])
best = max(best, dp[r][c])
return best * best
def cherry_pickup(grid: List[List[int]]) -> int:
"""Two walkers go from (0,0) to (n-1,n-1) at the same speed; a shared cell counts once.
grid values: 1 cherry, 0 empty, -1 thorn. Returns 0 if no path exists."""
n = len(grid)
NEG = float("-inf")
# dp[r1][r2] after t steps: walker 1 at (r1, t-r1), walker 2 at (r2, t-r2)
dp = [[NEG] * n for _ in range(n)]
dp[0][0] = grid[0][0]
for t in range(1, 2 * n - 1):
nd = [[NEG] * n for _ in range(n)]
lo, hi = max(0, t - n + 1), min(n - 1, t)
for r1 in range(lo, hi + 1):
c1 = t - r1
if grid[r1][c1] == -1:
continue
for r2 in range(r1, hi + 1): # symmetry: walker 1 is never below walker 2
c2 = t - r2
if grid[r2][c2] == -1:
continue
best = dp[r1][r2] # both moved right
if r1 > 0:
best = max(best, dp[r1 - 1][r2]) # walker 1 moved down
if r2 > 0:
best = max(best, dp[r1][r2 - 1]) # walker 2 moved down
if r1 > 0 and r2 > 0:
best = max(best, dp[r1 - 1][r2 - 1]) # both moved down
if best == NEG:
continue
gain = grid[r1][c1] + (grid[r2][c2] if r1 != r2 else 0)
nd[r1][r2] = best + gain
dp = nd
return max(0, dp[n - 1][n - 1]) # -inf (no path) becomes 0
if __name__ == "__main__":
assert calculate_minimum_hp([[-3, 5, -10], [-6, -2, 4], [2, -8, -1]]) == 4
assert calculate_minimum_hp([[1, -3, 3], [0, -2, 0], [-3, -3, -3]]) == 3
assert calculate_minimum_hp([[0]]) == 1
assert calculate_minimum_hp([[-5]]) == 6
assert calculate_minimum_hp([[100]]) == 1
m = [[1, 0, 1, 1, 1],
[1, 1, 1, 1, 1],
[0, 1, 1, 1, 1],
[1, 1, 1, 1, 0]]
assert maximal_square(m) == 9
assert maximal_square([[0]]) == 0
assert maximal_square([[1]]) == 1
ch = [[0, 1, 1, -1],
[1, 0, -1, 1],
[1, 1, 0, 1],
[-1, 1, 1, 0]]
assert cherry_pickup(ch) == 7
assert cherry_pickup([[1, 1, -1], [1, -1, 1], [-1, 1, 1]]) == 0
assert cherry_pickup([[1]]) == 1
print("all hard tests passed")
import java.util.Arrays;
public class GridHard {
static int calculateMinimumHP(int[][] rooms) {
int R = rooms.length, C = rooms[0].length;
int[][] need = new int[R + 1][C + 1];
for (int[] row : need) Arrays.fill(row, Integer.MAX_VALUE);
need[R][C - 1] = need[R - 1][C] = 1; // after the goal you must still be alive
for (int r = R - 1; r >= 0; r--)
for (int c = C - 1; c >= 0; c--) {
int next = Math.min(need[r + 1][c], need[r][c + 1]);
need[r][c] = Math.max(1, next - rooms[r][c]);
}
return need[0][0];
}
static int maximalSquare(int[][] m) {
int R = m.length, C = m[0].length, best = 0;
int[][] dp = new int[R + 1][C + 1]; // padded with a zero row and column
for (int r = 1; r <= R; r++)
for (int c = 1; c <= C; c++)
if (m[r - 1][c - 1] == 1) {
dp[r][c] = 1 + Math.min(dp[r - 1][c - 1], Math.min(dp[r - 1][c], dp[r][c - 1]));
best = Math.max(best, dp[r][c]);
}
return best * best;
}
static int cherryPickup(int[][] grid) {
int n = grid.length;
final int NEG = Integer.MIN_VALUE / 2;
int[][] dp = new int[n][n];
for (int[] row : dp) Arrays.fill(row, NEG);
dp[0][0] = grid[0][0];
for (int t = 1; t < 2 * n - 1; t++) {
int[][] nd = new int[n][n];
for (int[] row : nd) Arrays.fill(row, NEG);
int lo = Math.max(0, t - n + 1), hi = Math.min(n - 1, t);
for (int r1 = lo; r1 <= hi; r1++) {
int c1 = t - r1;
if (grid[r1][c1] == -1) continue;
for (int r2 = r1; r2 <= hi; r2++) { // symmetry: r1 <= r2
int c2 = t - r2;
if (grid[r2][c2] == -1) continue;
int best = dp[r1][r2];
if (r1 > 0) best = Math.max(best, dp[r1 - 1][r2]);
if (r2 > 0) best = Math.max(best, dp[r1][r2 - 1]);
if (r1 > 0 && r2 > 0) best = Math.max(best, dp[r1 - 1][r2 - 1]);
if (best == NEG) continue;
nd[r1][r2] = best + grid[r1][c1] + (r1 != r2 ? grid[r2][c2] : 0);
}
}
dp = nd;
}
return Math.max(0, dp[n - 1][n - 1]);
}
public static void main(String[] args) {
check(calculateMinimumHP(new int[][]{{-3, 5, -10}, {-6, -2, 4}, {2, -8, -1}}) == 4);
check(calculateMinimumHP(new int[][]{{1, -3, 3}, {0, -2, 0}, {-3, -3, -3}}) == 3);
check(calculateMinimumHP(new int[][]{{0}}) == 1);
check(calculateMinimumHP(new int[][]{{-5}}) == 6);
check(calculateMinimumHP(new int[][]{{100}}) == 1);
int[][] m = {{1, 0, 1, 1, 1}, {1, 1, 1, 1, 1}, {0, 1, 1, 1, 1}, {1, 1, 1, 1, 0}};
check(maximalSquare(m) == 9);
check(maximalSquare(new int[][]{{0}}) == 0);
check(maximalSquare(new int[][]{{1}}) == 1);
int[][] ch = {{0, 1, 1, -1}, {1, 0, -1, 1}, {1, 1, 0, 1}, {-1, 1, 1, 0}};
check(cherryPickup(ch) == 7);
check(cherryPickup(new int[][]{{1, 1, -1}, {1, -1, 1}, {-1, 1, 1}}) == 0);
check(cherryPickup(new int[][]{{1}}) == 1);
System.out.println("all hard tests passed");
}
static void check(boolean ok) {
if (!ok) throw new AssertionError("test failed");
}
}
#include <algorithm>
#include <cassert>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
int calculateMinimumHP(const vector<vector<int>>& rooms) {
int R = rooms.size(), C = rooms[0].size();
vector<vector<int>> need(R + 1, vector<int>(C + 1, INT_MAX));
need[R][C - 1] = need[R - 1][C] = 1; // after the goal you must still be alive
for (int r = R - 1; r >= 0; r--)
for (int c = C - 1; c >= 0; c--) {
int next = min(need[r + 1][c], need[r][c + 1]);
need[r][c] = max(1, next - rooms[r][c]);
}
return need[0][0];
}
int maximalSquare(const vector<vector<int>>& m) {
int R = m.size(), C = m[0].size(), best = 0;
vector<vector<int>> dp(R + 1, vector<int>(C + 1, 0)); // zero row and column as padding
for (int r = 1; r <= R; r++)
for (int c = 1; c <= C; c++)
if (m[r - 1][c - 1] == 1) {
dp[r][c] = 1 + min(dp[r - 1][c - 1], min(dp[r - 1][c], dp[r][c - 1]));
best = max(best, dp[r][c]);
}
return best * best;
}
int cherryPickup(const vector<vector<int>>& grid) {
int n = grid.size();
const int NEG = INT_MIN / 2;
vector<vector<int>> dp(n, vector<int>(n, NEG));
dp[0][0] = grid[0][0];
for (int t = 1; t < 2 * n - 1; t++) {
vector<vector<int>> nd(n, vector<int>(n, NEG));
int lo = max(0, t - n + 1), hi = min(n - 1, t);
for (int r1 = lo; r1 <= hi; r1++) {
int c1 = t - r1;
if (grid[r1][c1] == -1) continue;
for (int r2 = r1; r2 <= hi; r2++) { // symmetry: r1 <= r2
int c2 = t - r2;
if (grid[r2][c2] == -1) continue;
int best = dp[r1][r2];
if (r1 > 0) best = max(best, dp[r1 - 1][r2]);
if (r2 > 0) best = max(best, dp[r1][r2 - 1]);
if (r1 > 0 && r2 > 0) best = max(best, dp[r1 - 1][r2 - 1]);
if (best == NEG) continue;
nd[r1][r2] = best + grid[r1][c1] + (r1 != r2 ? grid[r2][c2] : 0);
}
}
dp.swap(nd);
}
return max(0, dp[n - 1][n - 1]);
}
int main() {
assert(calculateMinimumHP({{-3, 5, -10}, {-6, -2, 4}, {2, -8, -1}}) == 4);
assert(calculateMinimumHP({{1, -3, 3}, {0, -2, 0}, {-3, -3, -3}}) == 3);
assert(calculateMinimumHP({{0}}) == 1);
assert(calculateMinimumHP({{-5}}) == 6);
assert(calculateMinimumHP({{100}}) == 1);
vector<vector<int>> m = {{1, 0, 1, 1, 1}, {1, 1, 1, 1, 1}, {0, 1, 1, 1, 1}, {1, 1, 1, 1, 0}};
assert(maximalSquare(m) == 9);
assert(maximalSquare({{0}}) == 0);
assert(maximalSquare({{1}}) == 1);
vector<vector<int>> ch = {{0, 1, 1, -1}, {1, 0, -1, 1}, {1, 1, 0, 1}, {-1, 1, 1, 0}};
assert(cherryPickup(ch) == 7);
assert(cherryPickup({{1, 1, -1}, {1, -1, 1}, {-1, 1, 1}}) == 0);
assert(cherryPickup({{1}}) == 1);
cout << "all hard tests passed\n";
return 0;
}
function calculateMinimumHP(rooms: number[][]): number {
const R = rooms.length, C = rooms[0].length;
const need: number[][] = Array.from({ length: R + 1 }, () => new Array<number>(C + 1).fill(Infinity));
need[R][C - 1] = need[R - 1][C] = 1; // after the goal you must still be alive
for (let r = R - 1; r >= 0; r--)
for (let c = C - 1; c >= 0; c--) {
const next = Math.min(need[r + 1][c], need[r][c + 1]);
need[r][c] = Math.max(1, next - rooms[r][c]);
}
return need[0][0];
}
function maximalSquare(m: number[][]): number {
const R = m.length, C = m[0].length;
const dp: number[][] = Array.from({ length: R + 1 }, () => new Array<number>(C + 1).fill(0));
let best = 0;
for (let r = 1; r <= R; r++)
for (let c = 1; c <= C; c++)
if (m[r - 1][c - 1] === 1) {
dp[r][c] = 1 + Math.min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1]);
best = Math.max(best, dp[r][c]);
}
return best * best;
}
function cherryPickup(grid: number[][]): number {
const n = grid.length;
const fresh = (): number[][] => Array.from({ length: n }, () => new Array<number>(n).fill(-Infinity));
let dp = fresh();
dp[0][0] = grid[0][0];
for (let t = 1; t < 2 * n - 1; t++) {
const nd = fresh();
const lo = Math.max(0, t - n + 1), hi = Math.min(n - 1, t);
for (let r1 = lo; r1 <= hi; r1++) {
const c1 = t - r1;
if (grid[r1][c1] === -1) continue;
for (let r2 = r1; r2 <= hi; r2++) { // symmetry: r1 <= r2
const c2 = t - r2;
if (grid[r2][c2] === -1) continue;
let best = dp[r1][r2];
if (r1 > 0) best = Math.max(best, dp[r1 - 1][r2]);
if (r2 > 0) best = Math.max(best, dp[r1][r2 - 1]);
if (r1 > 0 && r2 > 0) best = Math.max(best, dp[r1 - 1][r2 - 1]);
if (best === -Infinity) continue;
nd[r1][r2] = best + grid[r1][c1] + (r1 !== r2 ? grid[r2][c2] : 0);
}
}
dp = nd;
}
return Math.max(0, dp[n - 1][n - 1]);
}
function check(ok: boolean, msg = "test failed"): void {
if (!ok) throw new Error(msg);
}
check(calculateMinimumHP([[-3, 5, -10], [-6, -2, 4], [2, -8, -1]]) === 4);
check(calculateMinimumHP([[1, -3, 3], [0, -2, 0], [-3, -3, -3]]) === 3);
check(calculateMinimumHP([[0]]) === 1);
check(calculateMinimumHP([[-5]]) === 6);
check(calculateMinimumHP([[100]]) === 1);
check(maximalSquare([[1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [0, 1, 1, 1, 1], [1, 1, 1, 1, 0]]) === 9);
check(maximalSquare([[0]]) === 0);
check(maximalSquare([[1]]) === 1);
check(cherryPickup([[0, 1, 1, -1], [1, 0, -1, 1], [1, 1, 0, 1], [-1, 1, 1, 0]]) === 7);
check(cherryPickup([[1, 1, -1], [1, -1, 1], [-1, 1, 1]]) === 0);
check(cherryPickup([[1]]) === 1);
console.log("all hard tests passed");
Notes on the choices: the dungeon uses a sentinel row and column filled with "infinity" except the two cells next to the goal, so the loop has no edge cases. Maximal square pads the table with a zero row and column for the same reason. Cherry pickup uses NEG = INT_MIN / 2 in Java and C++ so that adding a few cherries to "impossible" can never overflow into a valid-looking number (the code also skips impossible states explicitly).
Real-world uses
- Seam carving (content-aware image resizing). Avidan and Shamir (SIGGRAPH 2007) remove the vertical "seam" of pixels with the least energy:
M[r][c] = e[r][c] + min(M[r-1][c-1], M[r-1][c], M[r-1][c+1])— a minimum falling path sum. Repeat to shrink an image without squashing faces. Implemented in ImageMagick (-liquid-rescale) and GIMP's Liquid Rescale plug-in. - Sequence alignment. Needleman–Wunsch (1970) and Smith–Waterman (1981) align DNA or protein sequences by filling a grid where the axes are the two sequences and moves are right (gap), down (gap) and diagonal (match/mismatch). It is min path sum with three move types; see Sequence DP.
- Dynamic time warping (DTW). Compares two time series that run at different speeds (speech, gestures, sensor traces) with the same right/down/diagonal grid recurrence (Sakoe and Chiba, 1978).
diffand version control. Line-based diff is a shortest path in the "edit graph" grid of two files (Myers, 1986). Myers' algorithm is clever about which part of the grid to explore, but the grid is the model.- Stereo vision. Classic scanline stereo matching aligns a row of the left image with a row of the right image by DP on a grid of (left pixel, right pixel) pairs.
- Robot and game path planning on lattices. When movement is monotone (a conveyor, a scrolling game, a time axis), grid DP replaces graph search.
- Pascal's triangle and binomial tables. Any library that tabulates modulo a prime with the additive rule is running the unique-paths DP.
Pitfalls & edge cases
- Wrong loop order. Filling the dungeon top-down reads cells that are still "infinity". Rule: write down which neighbours the formula reads, then pick the order that finishes them first.
- Forgetting that rocks break the first row and column. Initialising
dp[0][c] = 1for the whole top row ignores a rock in the top row. Let the general rule handle the borders (as the rolling-array code does) instead of special-casing them. - Start or goal blocked. Both must return 0 paths (or "impossible"), not crash.
- Counting the start cell twice, or not at all. In min path sum,
dp[0][0] = cost[0][0], not 0. In the dungeon, the start room's effect must be applied (the−3in the example). - The
max(1, …)in the dungeon. Without it, a big potion produces "need ≤ 0", which then lets earlier demons look free. - Using the rolling row and then trying to reconstruct the path. The old rows are gone.
- Overflow in counts. 32-bit overflows from 18×18, 64-bit from 35×35; JavaScript numbers lose exactness past (from 30×30).
- Cherry pickup with an unreachable goal. The answer is 0, not and not a negative number.
- Cherry pickup: counting a shared cell twice. Only add the second walker's cell when
r1 != r2. - Maximal square returns the side, but the problem wants the area (or the other way round). Read the output spec.
- Non-square grids.
RandCare different; mixing them up passes square tests and fails rectangular ones. Always test a 1×N and an N×1 grid. - Four-direction movement. Grid DP silently gives wrong answers because the dependency graph has cycles. Use BFS/Dijkstra, or memoised DFS only if values strictly increase along every allowed move (which makes it a DAG again).
Variations
- Falling path sum / triangle. Moves go to the next row (straight, or diagonally left/right). Fill row by row; for the triangle, bottom-up avoids edge checks.
- Extra dimension for a side constraint. "Path sum divisible by " →
dp[r][c][sum mod k]; "at most obstacles removed on a right/down path" →dp[r][c][removed]. Time multiplies by the size of the new dimension. - Counting on huge grids with few blocked cells. Sort the blocked cells;
bad[i]= paths from the start to blocked cell that touch no earlier blocked cell . with precomputed factorials (Codeforces 559C "Gerald and Giant Chess"). - Longest increasing path in a matrix. Moves go in four directions but only to a strictly larger value, so the graph is a DAG; memoised DFS is a DAG DP.
- Maximal rectangle. Histogram per row + monotonic stack.
- Two robots moving down rows (Cherry Pickup II). State
(row, col1, col2), nine predecessor pairs. - Tiling a grid (dominoes, profiles). When the state must remember which cells of the current column are already covered, the grid DP becomes Broken-Profile DP.
- Speed-ups. Most grid DPs are already linear in the input. When a transition takes a min over a whole window of the previous row ("jump up to cells"), a monotonic deque or prefix sums bring it back to per cell; see DP Optimizations.
Practice ladder
Each problem is described in my own words; follow the link for the full statement.
1. Unique Paths (LeetCode 62) — Count right/down routes across an empty board. Teaches the basic recurrence and the rolling row.
Hint
dp[c] += dp[c-1], row after row. Or the binomial formula.
2. Unique Paths II (LeetCode 63) — The same, with blocked cells. Teaches zeroing blocked cells and letting borders fall out of the general rule.
Hint
A blocked cell sets dp[c] = 0. The code in this lesson is a full solution.
3. Minimum Path Sum (LeetCode 64) — Cheapest right/down route by cell tolls. Teaches min-plus transitions.
Hint
dp = min(up, left) + cost. You can even overwrite the input grid in place.
4. Triangle (LeetCode 120) — Cheapest top-to-bottom route through a triangle of numbers, stepping to one of the two numbers below. Teaches bottom-up filling to dodge edge cases.
Solution
Start from the bottom row; each number above adds the smaller of its two children. The top is the answer. time, space.
def minimum_total(tri):
best = tri[-1][:] # bottom row: cost from there is the value itself
for row in reversed(tri[:-1]):
best = [v + min(best[i], best[i + 1]) for i, v in enumerate(row)]
return best[0]
assert minimum_total([[4], [7, 2], [1, 8, 5], [6, 3, 9, 2]]) == 13
5. Grid Paths (CSES 1638) — Count routes on an board with traps, modulo . Teaches the obstacle DP under a modulus, and the "start is trapped" edge case.
Solution
MOD = 10**9 + 7
def grid_paths(rows):
n = len(rows)
dp = [0] * n
dp[0] = 1 if rows[0][0] == "." else 0
for r in range(n):
for c in range(n):
if rows[r][c] == "*":
dp[c] = 0
elif c > 0:
dp[c] = (dp[c] + dp[c - 1]) % MOD
return dp[-1]
assert grid_paths(["....", ".*..", "...*", "*..."]) == 3
6. Grid 1 (AtCoder DP Contest H) — Same idea on an board with walls. Good for practising fast input and modular counting.
Hint
Identical to the previous problem with a rectangular grid. Test 1×N and N×1.
7. Minimum Falling Path Sum (LeetCode 931) — Cheapest top-to-bottom route where each step goes straight down or diagonally. Teaches three-way transitions and the seam-carving recurrence.
Hint
dp[r][c] = cost + min(dp[r-1][c-1], dp[r-1][c], dp[r-1][c+1]), guarding the edges. Answer: min of the last row.
8. Maximal Square (LeetCode 221) — Largest all-1 square. Teaches "pin a corner" states and min-of-three.
Hint
side = 1 + min(up, left, diag); return best * best.
9. Count Square Submatrices with All Ones (LeetCode 1277) — Count every all-1 square. Teaches reinterpreting the same table.
Solution
A corner with side is the corner of exactly squares, so sum the table.
def count_squares(m):
R, C = len(m), len(m[0])
dp = [[0] * (C + 1) for _ in range(R + 1)]
total = 0
for r in range(1, R + 1):
for c in range(1, C + 1):
if m[r - 1][c - 1]:
dp[r][c] = 1 + min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1])
total += dp[r][c] # a side-k corner ends exactly k squares
return total
assert count_squares([[1, 1, 0, 1], [1, 1, 1, 1], [0, 1, 1, 1]]) == 13
10. Dungeon Game (LeetCode 174) — Minimum starting health to survive a monster-and-potion grid. Teaches backward state definitions.
Hint
need = max(1, min(down, right) - room), filled from the goal. Sentinels of 1 just past the goal.
11. Paths in Matrix Whose Sum Is Divisible by K (LeetCode 2435) — Count right/down routes whose sum is a multiple of . Teaches adding a remainder dimension.
Solution
dp[c][rem] for the current row: number of routes to this cell with sum ≡ rem. .
MOD = 10**9 + 7
def paths_divisible(grid, k):
C = len(grid[0])
dp = [[0] * k for _ in range(C)] # dp[c][rem] for the current row
for r, row in enumerate(grid):
for c, v in enumerate(row):
if r == 0 and c == 0:
dp[0] = [0] * k
dp[0][v % k] = 1
continue
up = dp[c] if r > 0 else [0] * k
left = dp[c - 1] if c > 0 else [0] * k
new = [0] * k
for rem in range(k):
new[(rem + v) % k] = (up[rem] + left[rem]) % MOD
dp[c] = new
return dp[C - 1][0]
assert paths_divisible([[4, 1, 2], [2, 5, 1], [1, 3, 5]], 3) == 2
12. Longest Increasing Path in a Matrix (LeetCode 329) — Longest route moving in four directions to strictly larger values. Teaches spotting a hidden DAG.
Solution
Strictly increasing values mean no cycles, so memoised DFS is safe. .
from functools import lru_cache
def longest_increasing_path(m):
R, C = len(m), len(m[0])
@lru_cache(maxsize=None)
def go(r, c):
best = 1
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and m[nr][nc] > m[r][c]:
best = max(best, 1 + go(nr, nc))
return best
return max(go(r, c) for r in range(R) for c in range(C))
assert longest_increasing_path([[3, 4, 5], [2, 9, 6], [1, 8, 7]]) == 9
For very large grids, replace recursion with a topological order (process cells by decreasing value).
13. Cherry Pickup II (LeetCode 1463) — Two robots start in the top corners and move down one row per step (down-left, down, down-right). Teaches lockstep walkers where the tick is the row.
Solution
State (a, b) = the two robots' columns on the current row; nine predecessor pairs; a shared cell counts once. .
def cherry_pickup_ii(grid):
R, C = len(grid), len(grid[0])
NEG = float("-inf")
dp = [[NEG] * C for _ in range(C)]
dp[0][C - 1] = grid[0][0] + (grid[0][C - 1] if C > 1 else 0)
for r in range(1, R):
nd = [[NEG] * C for _ in range(C)]
for a in range(C):
for b in range(C):
prev = max((dp[a + da][b + db]
for da in (-1, 0, 1) for db in (-1, 0, 1)
if 0 <= a + da < C and 0 <= b + db < C), default=NEG)
if prev != NEG:
nd[a][b] = prev + grid[r][a] + (grid[r][b] if a != b else 0)
dp = nd
return max(max(row) for row in dp)
assert cherry_pickup_ii([[2, 0, 4], [1, 6, 1], [3, 2, 5], [0, 4, 1]]) == 26
14. Cherry Pickup (LeetCode 741) — The round trip from this lesson. Teaches reversing the return trip and synchronising by anti-diagonal.
Hint
State (t, r1, r2), four predecessors, count a shared cell once, return max(0, …). The code above is a full solution.
15. Gerald and Giant Chess (Codeforces 559C) — Count routes on a board with up to 2000 black cells. Teaches when the table is too big and combinatorics + inclusion–exclusion take over.
Hint
Sort black cells (and the goal) by (row, column). f[i] = routes from the start to cell avoiding earlier black cells = . Precompute factorials mod .
Common mistakes & interview follow-ups
"Can you do it in O(n) memory?" Yes for totals: keep one row (min path sum, unique paths, dungeon, maximal square with one extra variable for the old diagonal). Say up front that this loses path reconstruction, and offer one direction bit per cell if they also want the path.
"What if the robot can also move left or up?" Then the grid is not a DAG and the DP's fill order does not exist. Unit costs → BFS; non-negative tolls → Dijkstra (); negative tolls with cycles → the problem may be unbounded.
"Why fill the dungeon backwards? Can you do it forwards?" Explain the two conflicting facts (lowest dip vs current health) and give a counterexample. Offer the forwards-with-binary-search alternative.
"Why min of three in maximal square, not min of two?" Up and left can both be large while the diagonal is small: the top-left corner of the would-be square is then missing. Example: a 3×3 block of 1s with the top-left cell set to 0 — up = left = 2 at the bottom-right corner, but the diagonal is 1, and the true answer is side 2.
"Why not run the best single path twice for cherry pickup?" Show the 4×4 counterexample (greedy 9, optimal 10). Then derive lockstep walkers.
"Count the paths modulo a prime on a grid." The table has cells — too many. Use the binomial formula with factorials; with obstacles, inclusion–exclusion over obstacles.
"Print all minimum paths." There can be exponentially many (a grid of zeros has ). Offer to count them (a second DP that adds counts from neighbours achieving the min) or to print them lazily.
Mistakes interviewers watch for: off-by-one between the grid and a padded table; initialising the whole top row to 1 when rocks exist; forgetting max(1, …); returning -inf for an impossible cherry pickup; loops in the wrong order; int overflow on path counts.
Quick quiz
1. In the 3×4 unique-paths table, which two cells does (2,2) read, and what is its value?
Answer
(1,2) = 3 and (2,1) = 3, so (2,2) = 6.
2. In the min-path-sum dry run, cell (1,3) reads up = 10 and left = 9. Why does the final route not pass through (1,3) even though it takes the smaller of its options?
Answer
Each cell picks its own best predecessor, but the goal (2,3) compares (1,3) = 17 with (2,2) = 11 and takes (2,2). A cell being filled well says nothing about whether the final route uses it; only the walk back from the goal decides that.
3. In the dungeon example, room (1,2) is a +4 potion and the next room needs 2. What does the formula give, and why is the answer not −2?
Answer
max(1, 2 − 4) = 1. You cannot enter a room with 0 or less health — you would already be dead — so the requirement never goes below 1.
4. In cherry pickup, why can two walkers only share a cell at the same tick?
Answer
A cell (r,c) is reached after exactly r + c moves by any right/down walk. Both walkers move once per tick, so each can be at (r,c) only at tick r + c.
5. A grid has 4-direction moves and positive tolls. Which algorithm do you use, and why does grid DP fail?
Answer
Dijkstra. With moves in all directions the cell dependencies form cycles, so there is no order in which each cell's predecessors are finished first.
6. What does the sum of all entries of the maximal-square side table count?
Answer
The number of all-1 square submatrices: a cell with side is the bottom-right corner of exactly of them. For the lesson's matrix, the table sums to 26.
Further reading / sources
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed. — Chapter 14 (dynamic programming: optimal substructure, the cut-and-paste argument, reconstruction; §14.4 LCS as a grid DP).
- Jon Kleinberg and Éva Tardos, Algorithm Design (2005) — §6.6–6.7 (sequence alignment as a grid shortest path, and Hirschberg's linear-space reconstruction).
- Shai Avidan and Ariel Shamir, "Seam Carving for Content-Aware Image Resizing", ACM Transactions on Graphics 26(3), SIGGRAPH 2007.
- Saul B. Needleman and Christian D. Wunsch, "A general method applicable to the search for similarities in the amino acid sequence of two proteins", Journal of Molecular Biology 48(3), 1970.
- Hiroaki Sakoe and Seibi Chiba, "Dynamic programming algorithm optimization for spoken word recognition", IEEE Transactions on Acoustics, Speech, and Signal Processing 26(1), 1978.
- Eugene W. Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica 1, 1986.
- cp-algorithms, Dynamic Programming and Finding the largest zero submatrix.
- AtCoder Educational DP Contest, problem list — problem H is grid counting.
Lessons: previous — String DP · next — Interval DP · module — Dynamic Programming · course — DSA: Zero to Mastery.
Related Archon pages: Matrices & Grids · BFS in Depth · Shortest Paths · Topological Sort · Sequence DP · String DP · DAG DP · Monotonic Stack & Deque.