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].
The two dimensions should have a reason. They might represent two positions, a position and a capacity, a row and a column, or the left and right boundaries of an interval.
Function Contract
count_grid_paths(rows, cols) expects positive integers rows and cols.
It returns the number of ways to move from the top-left cell to the bottom-right cell when movement is only down or right. dp[r][c] means the number of ways to reach cell (r, c).
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.
State Sentence
For the grid example:
dp[r][c] means the number of ways to reach cell (r, c).If movement is only down or right, the last step into (r, c) came from (r - 1, c) or (r, c - 1). That gives the recurrence:
dp[r][c] = dp[r - 1][c] + dp[r][c - 1]Boundary cells need special handling because one of those previous cells may not exist.
Table Size
If the first dimension has n possible values and the second has m, the table has n * m states. If each state is computed in constant time, the time and space are usually O(n * m).
If each state tries many transitions, multiply by the number of transitions.
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.
Another mistake is choosing a 2D table when one dimension is actually unnecessary. If the future only depends on one variable, 1D DP may be enough.
When To Use It
Use 2D DP when the current answer depends on two independent positions, capacities, strings, boundaries, or other state variables.
Before coding, write the exact meaning of dp[i][j]. Without that sentence, the nested loops are mostly guesswork.
The Main Point
2D DP fits when two variables are needed to identify one subproblem. The meaning of dp[i][j] must be clear before loops are written.