2D Dynamic Programming

When one dimension isn't enough — grid paths, string alignment, and the classic 2D DP table where states live at the intersection of two sequences.

12 min readLeetCode Patterns for InterviewsCode

The Pattern

2D DP extends 1D DP to two independent dimensions. The state dp[i][j] depends on dp[i-1][j], dp[i][j-1], and sometimes dp[i-1][j-1]. The table is built row-by-row or column-by-column, and each cell answers the question: 'what's the optimal value for these prefixes?'

Think of it as solving the problem for every pair of prefixes. For grid problems, dp[i][j] is the answer for the subgrid from (0,0) to (i,j). For string problems, dp[i][j] involves the first i characters of string A and first j characters of string B.

LCS table for 'ABC' vs 'AC' — match cells highlighted

	A	C
	0	0
A	1	1
B	1	1
C	1	2

dp[0][0]→dp[1][1]

dp[2][1]→dp[3][2]

2D DP is a table — fill it one cell at a time

Always draw the 2D table. The recurrence tells you which neighboring cells to look at. dp[i][j] usually needs dp[i-1][j], dp[i][j-1], or dp[i-1][j-1]. Build the table systematically and the answer is dp[m][n].

Grid DP Template

Gogrid-dp-—-unique-paths-(start-→-finish-counting-ways).go

17 linesLn 1, Col 1Go

Base: top row and left column are all 1 (only one way to reach them). Recurrence: reach (i,j) from above (i-1,j) or left (i,j-1).

LCS Pattern

The Longest Common Subsequence (LCS) is the canonical 2D string DP. dp[i][j] = LCS of first i chars of text1 and first j chars of text2. If chars match, extend the LCS by 1. If not, carry forward the best from either direction.

Golcs-—-the-textbook-2d-string-dp.go

18 linesLn 1, Col 1Go

Match → extend the diagonal. Mismatch → take the max of left or above. The +1 padding around the table simplifies the base case (empty string LCS = 0).

When to Use

Grid path counting or minimizing cost (Unique Paths, Min Path Sum, Dungeon Game).
Comparing two sequences (LCS, Edit Distance, Shortest Common Supersequence).
Two independent variables that define the state (index in array A, index in array B).
dp[i][j] depends on dp[i-1][j], dp[i][j-1], dp[i-1][j-1] — classic 2D recurrence.
Both dimensions are bounded ≤ 1000 — 2D DP table with 10⁶ cells is fine.

Problems

#62Unique PathsMedium2D DP — grid counting · O(m·n) time · O(m·n) — can optimize to O(n) with 1D rolling array space #1143Longest Common SubsequenceMedium2D DP — string alignment · O(m·n) time · O(m·n) — can optimize to O(min(m,n)) space

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.

Stage 1 · Code

Dynamic Programming & Greedy