Solving optimization problems using a two-dimensional state space.
Solving optimization problems using a two-dimensional state space.
1D dynamic programming works whenever a single index can describe a subproblem: the first i houses, the first i steps. The moment a problem has two moving parts, two strings being compared, a position on a grid, an index paired with a remaining budget, the state needs two indices and the memo grows from an array into a table. dp[i][j] answers a question about a pair, and the final answer waits in one corner of the grid.
Everything from the 1D page carries over unchanged: state first, recurrence from the choices, base cases, then fill. What's new is geometry. Cells depend on their neighbors, the borders hold the trivial cases, and the fill order has to respect who reads whom.
Unique Paths is the cleanest entry: a robot walks from the top-left of a grid to the bottom-right moving only right or down, and the question is how many routes exist. The state sentence writes itself, dp[r][c] is the number of paths to that cell, and the recurrence falls out of the movement rule: every cell is entered from above or from the left, so dp[r][c] = dp[r - 1][c] + dp[r][c - 1]. The first row and column hold 1, since there's exactly one way to slide along an edge. Predict the center cell of a 3 × 3 grid before reading on.
It's 2: one path arrives from above, one from the left. The full table fills as 1, 1, 1 across the top, then 1, 2, 3, then 1, 3, 6, and the corner's 6 is the answer. The combinatorics agree: a 3 × 3 walk is 2 rights and 2 downs in some order, and choosing which 2 of the 4 moves go right gives exactly 6.
The deeper use of the second dimension is comparing sequences. Longest Common Subsequence asks how long a (not necessarily contiguous) shared subsequence two strings have, and the state is dp[i][j], the LCS of the first i characters of one string and the first j of the other. Two rules fill the whole table. When the characters at i and j match, they extend whatever the diagonal had: dp[i - 1][j - 1] + 1. When they don't, skip one or the other and keep the better: max(dp[i - 1][j], dp[i][j - 1]).
On "abcde" against "ace", the table climbs to 3 in the corner, the subsequence "ace" itself. The zero-th row and column stay 0 the whole time, because an empty prefix shares nothing with anything, and that border is what the first real cells read. Edit Distance runs on the same chassis with three choices per cell instead of two (insert, delete, replace), and converting "horse" to "ros" costs exactly 3 operations.
You might think 2D DP requires 2D input, grids and string pairs. The second dimension is just as often a budget that the input never mentions. Coin Change II counts the ways to make an amount from coin denominations: one-dimensional input, but the honest state is "considering the first i coins, how many ways make amount j". Target Sum hides the same shape behind plus and minus signs.
These counting tables carry the family's sharpest trap. Loop coins on the outside and amounts on the inside, and each combination is counted once, since coins join in a fixed order. Swap the loops and 1 + 2 and 2 + 1 both count, and the code quietly answers a different question. Neither version crashes. Only one matches the problem.
The 1D recipe, upgraded with geometry:
dp[i][j] is the ..." with both indices doing work: the LCS of the first i characters of one string and the first j of the other, the number of paths to row i column j. If one index isn't earning its place, the problem may be 1D.0 hold the trivial answers: empty prefixes, single-cell paths. A table sized (m + 1) × (n + 1) gives every recurrence a safe place to look without bounds checks.m. Sequence problems that read the diagonal need one saved variable before overwriting. Optimize after the full table works, never before.Four families cover the interview canon. Grid paths read up and left (Unique Paths, Minimum Path Sum). Sequence alignment reads up, left, and diagonal (LCS, Edit Distance, Distinct Subsequences, and at the deep end, Regular Expression Matching). Knapsack counting pairs items against a budget (Coin Change II, Target Sum). And interval DP turns the indices into a range: dp[i][j] for Burst Balloons means the best score from popping everything strictly between i and j, solved by choosing which balloon pops last, an O(n³) triple loop worth meeting before it meets you.
Recognition follows the dimensions: two sequences, a grid, or a quantity paired with a budget all point here. When someone says a DP problem is "hard", they usually mean the state has a dimension nobody wrote down.
The table is simple machinery. These five habits keep it answering the right question:
0 with anything, and converting an empty string costs exactly its length in insertions. Get the border right and the recurrence never needs an if-statement for boundaries.Two checks first: what exactly does dp[i][j] mean in Longest Common Subsequence, and what answers live in the table's zero-th row and column? Work the grids first, then the sequence pairs, then the hidden-budget counters:
Completed | Title | Status | Notes | Solution | |
|---|---|---|---|---|---|
unique_paths.py
def unique_paths(rows: int, cols: int) -> int:
# One way to reach anything in the first row or column
dp = [[1] * cols for _ in range(rows)]
for r in range(1, rows):
for c in range(1, cols):
# Every cell is entered from above or from the left
dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
return dp[rows - 1][cols - 1]longest_common_subsequence.py
def longest_common_subsequence(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
# Row and column 0 stand for the empty prefix
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
# Matching characters extend the diagonal's subsequence
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
# Otherwise carry the better of skipping either character
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]