2D Dynamic Programming — Complete FAANG Interview Guide

Problem Statement#

You are preparing for the hardest dynamic programming interview rounds at FAANG. You need to master the seven canonical 2D DP recurrences — the patterns that show up in Edit Distance, LCS, Burst Balloons, Stock Trading, and grid path problems.

Constraints:

• 1 <= m, n <= 1000 typical input size for grid and string DP
• O(m*n) time required for accepted solutions
• O(min(m, n)) space achievable via rolling rows
• Recurrence over two dimensions must be derivable on a whiteboard

Input:  Two strings, a grid, or an interval [i, j]
Output: Optimal value, count, or alignment over both dimensions

Why This Problem Matters#

2D Dynamic Programming is the dividing line between mid-level and senior FAANG candidates. While 1D DP is expected, the ability to design a dp[i][j] state and articulate its transition under interview time pressure is what gets candidates past the hard rounds at Google, Meta, Amazon, Apple, Microsoft, and Netflix. Edit Distance, LCS, Burst Balloons, and Stock Trading patterns are interview staples precisely because they force the candidate to reason about two interacting indices.

In real systems, 2D DP appears in spell checkers and autocomplete (Edit Distance), version control diff algorithms (LCS), pricing optimization (Stock state machines), and bioinformatics sequence alignment. Understanding the seven patterns below also unlocks pattern transfer — once you understand the LCS recurrence, Shortest Common Supersequence, Delete Operations for Two Strings, and Min ASCII Delete Sum become trivial variants.

This guide is the entry point for all 22 problems in the dsa-dp-2d series. Master these seven templates and you will recognize any 2D DP within 60 seconds of reading the prompt.

The Core Insight#

Every 2D DP problem follows the same derivation: define dp[i][j] over two indices (string positions, grid coordinates, or interval endpoints), write the transition that depends only on smaller (i, j) pairs, set the boundary row and column, and decide a topological iteration order. The hardest part is recognizing the second dimension — sometimes it is a second string, sometimes a remaining transaction count, sometimes the right endpoint of an interval.

The 7 Core 2D DP Patterns#

Pattern 1 — LCS / Sequence Alignment#

dp[i][j] = answer for s1[:i] and s2[:j].

if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Problems: LCS, Longest Common Substring, Shortest Common Supersequence.

Pattern 2 — Edit Distance / String Transform#

Cost to transform s1 into s2.

if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]
else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Problems: Edit Distance, Delete Operations, Min ASCII Delete Sum.

Pattern 3 — Grid Path Counting#

Number of paths from (0, 0) to (m-1, n-1).

dp[i][j] = dp[i-1][j] + dp[i][j-1]   if not obstacle

Problems: Unique Paths, Unique Paths II, Minimum Path Sum.

Pattern 4 — Interval DP#

Optimal value across all split points in [i, j].

dp[i][j] = best over k in [i, j-1] of dp[i][k] + dp[k+1][j] + cost(i, j, k)

Problems: Burst Balloons, Matrix Chain Multiplication, Strange Printer.

Pattern 5 — 2D Knapsack with Two Constraints#

Each item consumes two resources.

dp[i][j][k] = best using i items with constraints j and k

Problems: Ones and Zeroes, Last Stone Weight II.

Pattern 6 — Stock Trading State Machine#

State = (day, holding, transactions_left).

hold[i] = max(hold[i-1], cash[i-1] - price[i])
cash[i] = max(cash[i-1], hold[i-1] + price[i])

Problems: All six Best Time to Buy and Sell Stock variants.

Pattern 7 — Grid DP with Extra State#

Position plus extra state — broken obstacles, remaining turns.

dp[i][j][k] = best at (i, j) with k remaining

Problems: Dungeon Game, Cherry Pickup, Minimum Falling Path Sum II.

Visual Dry Run#

LCS of s1 = "ace" and s2 = "abcde" step by step.

Solution (Optimal)#

LCS template — applies to LCS, SCS, Delete Operations, and Min ASCII Delete Sum.

class Solution:
    def longestCommonSubsequence(self, s1: str, s2: str) -> int:
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[m][n]
 
    def minDistance(self, s1: str, s2: str) -> int:
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = i
        for j in range(n + 1):
            dp[0][j] = j
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
        return dp[m][n]

var longestCommonSubsequence = function(s1, s2) {
    const m = s1.length, n = s2.length;
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s1[i - 1] === s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
};
 
var minDistance = function(s1, s2) {
    const m = s1.length, n = s2.length;
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
    for (let i = 0; i <= m; i++) dp[i][0] = i;
    for (let j = 0; j <= n; j++) dp[0][j] = j;
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s1[i - 1] === s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
            }
        }
    }
    return dp[m][n];
};

Time: O(mn) — fill every cell once. Space: O(mn), reducible to O(min(m, n)) using rolling rows.

Complexity Reference#

Common Mistakes#

• Forgetting boundary row and column — dp[i][0] and dp[0][j] need explicit base cases.
• Confusing LCS with Longest Common Substring — substring requires contiguity, resets to 0 on mismatch.
• Iterating intervals by index instead of by length — interval DP must fill by increasing length.
• Reusing rolling row without saving the diagonal in Edit Distance — store the previous diagonal value before overwriting.
• Wrong state for stock variants — k transactions doubles the state dimension.

Interview Tips#

• Whiteboard the dp grid for small m, n before coding.
• Always state dp[i][j] definition explicitly — interviewers check this first.
• Mention rolling row optimization to show senior-level thinking.
• For interval DP, write the length loop on the outside.
• For stock problems, draw the state machine before writing code.

Follow-up Questions#

• Can you reconstruct the actual LCS string? — backtrack through the dp grid.
• Can you reduce space to O(min(m, n))? — yes, with rolling rows.
• What if edit costs differ? — replace the 1 + with cost-specific weights.
• How would you parallelize LCS for very long sequences? — anti-diagonal wavefront.
• What if the grid is sparse? — use hashed memoization keyed on (i, j).

Key Takeaways#

• 2D DP covers seven recurring patterns — LCS, Edit Distance, Grid Paths, Interval DP, 2D Knapsack, Stock, and Grid with State.
• Always articulate dp[i][j] semantics out loud before writing code.
• Most 2D DP can roll from O(m*n) space down to O(min(m, n)) with two rows.
• Interval DP must iterate by length, not by index — this is the most common bug.
• Stock state machines reduce all six LeetCode variants to one template.
• Edit Distance and LCS share boundary handling — master both together.
• This guide prepares you for 22 problems in the dsa-dp-2d series and any FAANG 2D DP question.

Problem Index#