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.

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]

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.

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]

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:

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:

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: