2-D DP¶
Also known as: Grid DP, Matrix DP, Two-Index DP
The state now needs two coordinates, so the table becomes a grid: each cell's answer is built from its neighbours above and to the left. Filling it in the right order is the whole job.
Before you start¶
What 'solved properly' looks like
Target: O(m × n). If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
Instead of a one-dimensional array, you build a grid where rows and columns each represent one dimension of the state. Each cell depends on the cell above, the cell to the left, or the diagonal — and you fill the grid in an order that guarantees those neighbours are already computed. The skill is recognising which neighbours matter for your problem, because that determines the recurrence.
Why it matters: It's the bridge from "DP is a line" to "DP is a shape." Grid-path problems like Unique Paths are the gentlest possible introduction to two-dimensional thinking, and every harder DP pattern — sequence comparison, knapsack, palindrome partitioning — is ultimately a 2-D table with a different recurrence.
When to reach for it¶
Reach for it when the problem involves a literal grid or matrix of paths from corner to corner, "unique paths", "minimum path sum", or any problem where two independent things vary (index in first sequence, index in second sequence).
When not to use it
Memory is the usual failure — most 2-D DP only ever reads the previous row, which means you can collapse it from O(m×n) to O(n). Base row and column initialisation is where the off-by-one bugs live; do it deliberately, not by reflex.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Unique Paths | LeetCode | Medium | 20 mins | teaching |
| 2 | Minimum Path Sum | LeetCode | Medium | 20 mins | teaching |
| 3 | Unique Paths II | LeetCode | Medium | 25 mins | consolidation |
| 4 | Triangle | LeetCode | Medium | 25 mins | consolidation |
| 5 | Maximal Square | LeetCode | Medium | 30 mins | challenge |
Already know this? Test out.
If you can solve Maximal Square cleanly in one sitting — recognising that each cell's square size depends on its three neighbours — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.