DSA & Algorithms
Part 20 of 21 · DSA Interview PatternsDynamic Programming — 2D, Knapsack & Grids — Paths, Subsets & LCS
2D DP for grids, 0/1 knapsack, LCS/edit distance, and space-optimized rolls.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Two indexes both belong in the state
Prefer
A grid, a knapsack row, or an LCS table
dp[i][j] is a path cell, a capacity, or a pair of string prefixes. You can often roll one dimension.
- 0/1 capacity walks backward so each item is used once.
- Unbounded capacity walks forward.
- LCS on a match takes the diagonal plus one.
Alternative
A 1D recurrence that cannot see both indexes
You will invent extra state in your head and get the indices wrong anyway.
- Forward 0/1 loops that reuse an item.
- Confusing LCS with a contiguous substring.
- Edit distance with a zero border instead of i and j.
Come from a neighbor
Up, left, or diagonal. The problem tells you which neighbors are legal.
- 1
Define dp[i][j]
Grid cell, item i at capacity j, or prefixes i and j. - 2
Pull from the legal neighbors
Min path, boolean OR, or max of up and left. - 3
Roll a row if the previous row is enough
Knapsack and unique paths often collapse to one array.
Overview
2D DP for grids, 0/1 knapsack, LCS/edit distance, and space-optimized rolls.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Use 2D DP for two indices (i,j), grids, LCS/edit distance, or knapsack with item index + capacity.
Recognition cues
- unique paths / min path sum
- 0/1 knapsack / partition equal subset
- longest common subsequence
- edit distance
Mental model
Decisions
- 1
1. State is dp i j
- next2. From up, left, or diag
- 2
2. From up, left, or diag
- next3. Grid or strings?
- ?
3. Grid or strings?
- grid4. Path or knapsack cell
- text5. LCS or edit distance
- 4
4. Path or knapsack cell
- next6. Roll one row when you can
- 5
5. LCS or edit distance
- next6. Roll one row when you can
- 6
6. Roll one row when you can
Lesson map
Dynamic Programming — 2D, Knapsack & Grids — Paths, Subsets & LCS
2D DP for grids, 0/1 knapsack, LCS/edit distance, and space-optimized rolls.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB cell["1. State is dp i j"] from["2. From up, left, or diag"] kind["3. Grid or strings?"] grid["4. Path or knapsack cell"] cell -->|1. State is dp i j| from from -->|2. From up, left, or diag| kind kind -->|grid| grid
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- Grid O(RC); knapsack O(nW); LCS O(mn).
- Often roll to O(min dimension) or O(W) space.
Common pitfalls & interview traps
LeetCode drill (real problems)
- Unique Paths
- Minimum Path Sum
- Partition Equal Subset Sum
- Longest Common Subsequence
- Edit Distance
- Target Sum
- Maximal Square
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
0/1 vs unbounded loop?
Answer
0/1 reverse capacity; unbounded forward.
LCS recurrence?
Answer
Match: diag+1; else max(up, left).
Edit distance ops?
Answer
Insert/delete/replace → left/up/diag transitions.
Grid space opt?
Answer
1D rolling over columns.
Subset sum?
Answer
Boolean knapsack toward target = total/2.
When 2D needed?
Answer
Two changing indices that both matter in state.