Dynamic Programming II — 2-D

The final pattern. When a problem involves two sequences or a grid, one index isn’t enough — you need a 2-D table. The idea is the same as 1-D DP (build each state from smaller ones); there’s just one more dimension.

The idea

Define dp[i][j] over two indices — usually “the answer considering the first i of one thing and the first j of another.” Each cell is built from its neighbours (the cell above, to the left, and/or diagonally up-left). Fill the table row by row; the answer is usually the bottom-right cell.

Worked example: unique paths (grid)

How many paths from top-left to bottom-right of an m×n grid, moving only right or down? Each cell is reached from above or from the left: dp[i][j] = dp[i-1][j] + dp[i][j-1]. (Compressed to 1-D since we only need the previous row.)

def unique_paths(m, n):
    dp = [1] * n                     # first row is all 1s
    for _ in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j-1]         # from above (dp[j]) + from left (dp[j-1])
    return dp[-1]
# unique_paths(3, 7) -> 28

Worked example: longest common subsequence

The canonical two-sequence DP. dp[i][j] = LCS length of the first i chars of A and first j of B. If the characters match, extend the diagonal; else take the best of dropping one character from either string:

def lcs(a, b):
    dp = [[0] * (len(b)+1) for _ in range(len(a)+1)]
    for i in range(1, len(a)+1):
        for j in range(1, len(b)+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1          # match → diagonal + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # best of up / left
    return dp[-1][-1]
# lcs("abcde", "ace") -> 3  ("ace")

Worked example: edit distance

Minimum insert/delete/replace operations to turn A into B. If chars match, no cost (diagonal); else 1 + min(insert, delete, replace):

def edit_distance(a, b):
    dp = [[0]*(len(b)+1) for _ in range(len(a)+1)]
    for i in range(len(a)+1): dp[i][0] = i          # delete all
    for j in range(len(b)+1): dp[0][j] = j          # insert all
    for i in range(1, len(a)+1):
        for j in range(1, len(b)+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j],     # delete
                                   dp[i][j-1],     # insert
                                   dp[i-1][j-1])   # replace
    return dp[-1][-1]
# edit_distance("horse", "ros") -> 3

Worked example: 0/1 knapsack

For each item, take it (gain its value, use its weight) or skip it — the archetype of “take or not take” DP. The 1-D compressed version iterates capacity backwards so each item is used once:

def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        for c in range(W, weights[i] - 1, -1):      # backwards → 0/1 (use each item once)
            dp[c] = max(dp[c], dp[c - weights[i]] + values[i])
    return dp[W]
# knapsack([1,3,4,5], [1,4,5,7], 7) -> 9

Knapsack-shaped DP (take/skip with a budget) underlies partition-equal-subset-sum, target-sum, and many “can you make exactly X” problems.

Step-by-step walkthrough

Here is the full LCS table for A = "abcde", B = "ace". Cell [i][j] is the LCS length of the first i letters of A and the first j letters of B. When the letters match, take the diagonal + 1; otherwise take the larger of up and left.

Fill it row by row; the answer is the bottom-right cell, 3 ("ace"). Notice each row only reads the row above — that’s why many 2-D DPs compress to a single 1-D array.

When to reach for it (and the 1-D compression)

Signals: two strings/arrays compared (LCS, edit distance, interleaving), grid paths (unique paths, min path sum, maximal square), subsequence problems, “min edits/operations”, or “can you partition/select to hit a target” (knapsack family). Many 2-D DPs compress to 1-D because each row only depends on the previous one — a nice optimisation to mention (O(n) space instead of O(n·m)).

Pitfalls

• Index/base-case errors. 2-D tables have whole base rows and columns (e.g. edit distance’s dp[i][0]=i). Initialise them carefully.
• Compressing too eagerly. The 1-D rolling optimisation is great, but get the full 2-D version correct first, then compress — and iterate in the right direction (knapsack goes backwards).
• Wrong neighbour. Match → diagonal; mismatch → up/left (or up/left/diagonal for edit distance). Draw a few cells by hand to confirm the recurrence.

Recap

2-D DP handles two sequences or a grid with a table dp[i][j], each cell built from its neighbours: unique paths (up + left), LCS (match → diagonal+1, else max of up/left), edit distance (1 + min of three), knapsack (take/skip with a budget). Fill row by row; the answer is the last cell; often compressible to 1-D. Signal: two strings/arrays, grid paths, subsequence, min-operations, partition-to-target.

Practice: 12 solved problems on 2-D dynamic programming → — cover each one, solve it yourself, then check the tested code.

You’ve finished the core 18 patterns

That’s the main toolkit — the patterns behind the large majority of coding-interview questions. For each one, learn the template by heart, work the practice set, and in the interview name the pattern out loud before you code. Recognition is the whole skill, and it only comes from deliberate practice.

Part II — Extended & Advanced Patterns

The core 18 get you through most rounds. The next lessons round out the toolkit for the harder end of the MAANG bar — a data-structures reference, the patterns that come up often but aren’t in the core set (tries, bit manipulation, greedy), and the genuinely advanced material senior/staff interviews probe (weighted-graph algorithms, advanced DP, string matching).

Next: Lesson 19 — Data Structures: Your Toolbox.