Dynamic programming · HTML
dp[r][c] denotes an answer reaching or leaving cell (r,c). With right/down movement, dp[r][c]=cell(r,c) ⊕ Aggregate(dp[r-1][c],dp[r][c-1]). Iteration must be a topological order.
Recognition signals
- A state is naturally a two-dimensional coordinate.
- Allowed movement directions make the dependency graph acyclic.
- Many paths share the same cell prefix or suffix.
- The objective is path count, minimum cost, or maximum reward.
- Each cell depends on a fixed directional neighborhood.
False friends
| Signal | Why it is different |
|---|
| Unrestricted four-way movement | A row scan is no longer topological; use BFS/Dijkstra for shortest paths or another cyclic-state method. |
| Connectivity only | When no path value is aggregated, DFS or BFS expresses the task directly. |
| A path bottleneck objective | With four-way movement and a maximum-along-path cost, minimax Dijkstra or answer search is a better model. |
Core invariant
When cell (r,c) is processed, every predecessor state already meets its definition; the new state aggregates every legal way to enter the cell exactly as required.
State, transition, and processing order
| Item | Definition |
|---|
| State | An optimum or count for coordinate (r,c), with an unreachable sentinel for blocked cells. |
| Transition | Aggregate all legal predecessors by min, max, or sum and combine with the current cell; initialize the start independently. |
| Frontier / order | A row/column topological order matching movement. If only the previous row and current left state matter, compress to one row. |
Python skeleton
def min_grid_cost(grid):
if not grid or not grid[0]: return 0
rows, cols = len(grid), len(grid[0])
dp = [float('inf')] * cols
dp[0] = 0
for r in range(rows):
for c in range(cols):
from_up = dp[c]
from_left = dp[c - 1] if c else float('inf')
if r == 0 and c == 0:
dp[c] = grid[r][c]
else:
dp[c] = grid[r][c] + min(from_up, from_left)
return dp[-1]
Correctness sketch
- The start is correctly initialized from its unique empty predecessor.
- Topological iteration makes the upper and left subanswers correct before use.
- Every path into the current cell has one legal final predecessor, so aggregating all such correct candidates is complete; induction reaches the destination.
Complexity
| Time | Space | Parameters |
|---|
| O(RC) | O(C) compressed or O(RC) for the full table | R and C are dimensions; a wider dependency radius needs more retained rows. |
Edge cases
- empty grid
- one row or column
- blocked start or destination
- arithmetic with unreachable sentinels
- negative costs on an acyclic grid
- update order under compression
Error patterns
| Pattern | Why it fails / fix |
|---|
| Scanning against dependency direction | A transition reads an unfinished or overwritten state; draw arrows before loops. |
| Scattered first-row special cases | Sentinels or a padded border can unify transitions and reduce branching. |
| Treating a cyclic grid as a DAG | Four-way movement creates cycles, so one scan cannot finalize states. |
| Overwriting the upper value | In one-row compression, dp[c] is the old row while dp[c-1] is the new row. |
Selection and exclusion rules
- Confirm that movement dependencies are acyclic.
- Choose reaching versus leaving state semantics and matching traversal.
- Use a sentinel to unify boundaries and unreachable cells.
- Compress only after dependency radius and update order are explicit.
| Relation | Template | Boundary |
|---|
| adjacent, not interchangeable | Grid flood fill | Moves form a DAG and the goal is counting or optimization. |
| dimensional-extension | Linear dynamic programming | The two-dimensional topological state extends linear DP. |
Original micro-example
| Part | Detail |
|---|
| Result | The minimum route passes through the lower-left cell and costs 6. |
| Setup | Costs are [[2,5],[1,3]], with only right or down moves. |
| Trace | Left-bottom costs 3, right-top 7; bottom-right is min(3,7)+3=6. |
Recall prompts
My notes