2D dynamic programming uses two variables to describe each state. The table is usually a grid of values.
It appears when one index is not enough to describe the subproblem.
Core Idea
A state such as dp[i][j] might describe a grid cell, a pair of string prefixes, an item index and remaining capacity, or a range boundary.
The recurrence must say which neighboring or earlier states determine dp[i][j].
Python Example
def count_grid_paths(rows, cols):
dp = [[0] * cols for _ in range(rows)]
dp[0][0] = 1
for r in range(rows):
for c in range(cols):
if r > 0:
dp[r][c] += dp[r - 1][c]
if c > 0:
dp[r][c] += dp[r][c - 1]
return dp[-1][-1]Each cell depends on the cell above and the cell to the left.
Common Confusions
2D DP is not automatically about physical grids. The two dimensions can represent any two state variables.
The table can become large quickly. If there are n values for one variable and m values for the other, the table has n * m states.
When To Use It
Use 2D DP when the current answer depends on two independent positions, capacities, strings, boundaries, or other state variables.