When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Grid routes
- Two-sequence state
- Capacity plus index
When another approach fits better
- One dimension is derivable or can be rolled into constant state
- The task asks to enumerate all configurations rather than aggregate values/counts
How it works#
Recursively branch on both dimensions, recomputing the same coordinate pair or prefix pair.
Name both state dimensions and why each is necessary.
Derive transitions from the last move/choice.
Initialize the full boundary row/column, then consider rolling one dimension.
Invariantdp[i][j] has a fixed meaning at the intersection of two prefixes/coordinates, and iteration follows its dependency directions.
Example and template#
Unique Paths
Extends state and recurrence reasoning into two dimensions without advanced transitions.
Open the full problem brief- Grid state
dp[r][c] = paths to (r,c)Each coordinate is one reusable subproblem.
- Fill
dp[r][c] = up + leftThe final move must come from exactly one valid predecessor.
initialize dp boundary states
for i in row order:
for j in column order:
dp[i][j] = combine(valid predecessor states)
return dp[target_i][target_j]- Time
- O(rows × columns × transition work)
- Space
- O(rows × columns), sometimes one row
- Assumptions
- The dependency graph follows the chosen iteration order and each table state is reachable/defined.
Pitfalls#
Common wrong approaches
An incorrect first row/column propagates through every later state.
If each row needs only the prior row, retaining all rows wastes space.
Edge cases
- Empty dimension
- Blocked start or target
- One row/column
- Overflow in path counts
Interview narration
- “One index cannot describe both current prefixes, so I need two dimensions.”
- “This cell means the complete answer for exactly these prefixes.”
- “The iteration order guarantees every predecessor is already final.”
Practice#
Unique Paths
Extends state and recurrence reasoning into two dimensions without advanced transitions.
Practice this problemFind the minimum edits converting one string into another.
Reveal the pattern decision
Use prefix-pair DP because both consumed lengths affect the remaining decision.
Transfer problem
Maximize value under a capacity using each item at most once.
Checkpoint: Define item-prefix and capacity dimensions; reverse capacity if compressing to one row.
Follow-up variations
- Recover one optimal sequence
- Compress rows while retaining enough information for reconstruction
Error-log prompts
- Why was each dimension necessary?
- Were boundary states semantically correct?