2D DP where dp[i][j] depends on dp[i-1][j] and dp[i][j-1] (or similar neighbors), often with an obstacle or cost twist.
Sub-patterns
- A — Path Counting. How many distinct paths exist from one corner to another.
- B — Path Cost Minimization. Cheapest path from one corner to another.
- C — Obstacle Handling. Blocked cells that break the simple recurrence.
- D — Grid DP with Extra Carried State. State includes more than just position, e.g. remaining moves or collected items.
Practice set (7)
- Medium — Unique Paths, Unique Paths II, Minimum Path Sum, Triangle
- Hard — Dungeon Game, Cherry Pickup, Minimum Falling Path Sum II
Pending
Path Counting
Count the distinct paths from one corner of a grid to another.
Pending
Path Cost Minimization
Find the cheapest path from one corner of a grid to another.
Pending
Obstacle Handling
Blocked cells that break the simple neighbor-sum recurrence and need explicit handling.
Pending
Grid DP with Extra Carried State
State includes more than just position — remaining moves, collected items, or similar.
Notes from readers
Comments — via GitHub