2D DP Master Recap — FAANG Cheatsheet & Pattern Index

Problem Statement#

You have completed all 22 problems in the dsa-dp-2d series. This recap is your single reference page — every 2D transition, the stock state machine, the interval DP template, and LCS reconstruction in one printable cheatsheet for the day before your dynamic programming interview.

Constraints:

• Targets all 7 canonical 2D DP patterns
• Must encode every transition compactly enough to memorize in 45 minutes
• Must include the stock state machine for all six LeetCode variants
• Must include LCS reconstruction and interval DP iteration order

Input:  Any 2D DP problem (two strings, grid, or interval)
Output: The matching pattern, transition, and complexity in seconds

Why This Problem Matters#

2D Dynamic Programming is the hardest topic in FAANG dynamic programming interviews. The night before a Google, Meta, Amazon, Apple, or Microsoft on-site, candidates do not need new content — they need a dense, single-page reference that triggers immediate recall of the seven canonical 2D recurrences. This recap exists for that moment.

Edit Distance, LCS, Burst Balloons, and the Best Time to Buy and Sell Stock variants are interview staples because they probe state design over two indices simultaneously. Confusing the LCS recurrence with Edit Distance, or iterating interval DP by index instead of by length, is the single most common reason strong candidates fail the hard DP round. Use this page as your last-mile cheatsheet — every entry below has been chosen because it has saved a real interview.

The Core Insight#

Every 2D DP collapses to a state dp[i][j] where (i, j) indexes either two strings, two grid coordinates, or the two endpoints of an interval. The transition reaches back to strictly smaller (i, j) pairs, the boundary row and column form the base cases, and the iteration order is dictated by which subproblems must be filled first.

Pattern Reference#

Visual Dry Run#

Edit Distance of s1 = "horse" and s2 = "ros" step by step.

Solution (Optimal)#

The three most reused 2D DP templates in one place.

class Solution:
    def longestCommonSubsequence(self, s1, s2):
        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 maxProfitWithCooldown(self, prices):
        hold = -prices[0]
        sold = 0
        rest = 0
        for p in prices[1:]:
            prev_sold = sold
            sold = hold + p
            hold = max(hold, rest - p)
            rest = max(rest, prev_sold)
        return max(sold, rest)
 
    def maxCoins(self, nums):
        a = [1] + nums + [1]
        n = len(a)
        dp = [[0] * n for _ in range(n)]
        for length in range(2, n):
            for i in range(n - length):
                j = i + length
                for k in range(i + 1, j):
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j])
        return dp[0][n - 1]

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 maxProfitWithCooldown = function(prices) {
    let hold = -prices[0], sold = 0, rest = 0;
    for (let i = 1; i < prices.length; i++) {
        const prevSold = sold;
        sold = hold + prices[i];
        hold = Math.max(hold, rest - prices[i]);
        rest = Math.max(rest, prevSold);
    }
    return Math.max(sold, rest);
};
 
var maxCoins = function(nums) {
    const a = [1, ...nums, 1];
    const n = a.length;
    const dp = Array.from({ length: n }, () => new Array(n).fill(0));
    for (let length = 2; length < n; length++) {
        for (let i = 0; i + length < n; i++) {
            const j = i + length;
            for (let k = i + 1; k < j; k++) {
                dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
            }
        }
    }
    return dp[0][n - 1];
};

Time: LCS O(mn), Stock O(n), Interval DP O(n^3). Space: LCS O(mn) reducible to O(n), Stock O(1), Interval DP O(n^2).

Stock State Machine#

hold = max(hold, rest - price)
sold = hold + price
rest = max(rest, sold_prev)

This three-state machine handles cooldown, fee, and bounded transactions with minor tweaks — for k transactions extend to two arrays of size k+1.

Interval DP Template#

for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        dp[i][j] = INF
        for k in range(i, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost(i, j, k))

The outer loop is length, not index — this is the most common interval DP bug.

LCS Reconstruction#

i, j = m, n
result = []
while i > 0 and j > 0:
    if s1[i - 1] == s2[j - 1]:
        result.append(s1[i - 1])
        i -= 1
        j -= 1
    elif dp[i - 1][j] > dp[i][j - 1]:
        i -= 1
    else:
        j -= 1
result.reverse()

Backtrack through the dp grid from (m, n) to recover the actual subsequence.

Common Mistakes#

• Iterating interval DP by i, j directly instead of by length — fills cells before their dependencies.
• Forgetting boundary row and column in Edit Distance — dp[i][0] = i and dp[0][j] = j.
• Reusing rolling row in LCS without saving the diagonal — overwrites dp[i-1][j-1].
• Confusing LCS with Longest Common Substring — substring resets to 0 on mismatch.
• Wrong number of states for stock with k transactions — must include the transaction count dimension.

Interview Tips#

• Always state dp[i][j] semantics before writing code — interviewers grade this first.
• For interval DP, write the length loop on the outside and explain why.
• For stock variants, draw the state machine before writing transitions.
• Mention rolling row optimization to demonstrate senior-level thinking.
• If stuck, write the recursive memoized version first, then convert to bottom-up.

Follow-up Questions#

• Can you reconstruct the optimal LCS or edit script? — backtrack through the dp grid.
• Can you space-optimize 2D DP to O(min(m, n))? — yes with rolling rows and a saved diagonal.
• What if edit costs differ per operation? — replace 1 + with cost-specific weights.
• How do you parallelize LCS? — anti-diagonal wavefront across processors.
• What if k transactions exceeds n/2 in stock problems? — collapse to unbounded transactions.

Key Takeaways#

• Seven patterns cover the vast majority of 2D DP interview questions at FAANG.
• Always articulate dp[i][j] semantics before writing the transition.
• Interval DP must iterate by length on the outside — this is the most common bug.
• The three-state stock machine handles cooldown, fee, and k-transaction variants.
• LCS reconstruction backtracks through the dp grid from (m, n) to (0, 0).
• Rolling rows reduce O(m*n) to O(min(m, n)) — mention this to show senior thinking.
• This recap is the single reference for the night before your DP on-site.

Problem Index#

Grid Paths — Unique Paths (01, 02), Min Path Sum (03), Triangle (04).

LCS — LCS (05), Longest Common Substring (06), SCS (10), Delete Operations (08).

Edit Distance — Edit Distance (07), Min ASCII Delete Sum (09).

Interval DP — Burst Balloons (11), Strange Printer (12), Cut Stick (13).

Stock — All six variants covered (14 through 19).

Grid with State — Dungeon Game (20), Cherry Pickup (21).

2D Knapsack — Ones and Zeroes (22).