LC Patterns — Advanced DP (2D and Beyond)

2D bottom-up with padded borders (the default shape)

vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, 0));  // row/col 0 = empty prefix
for (int i = 1; i <= m; ++i)
    for (int j = 1; j <= n; ++j)
        dp[i][j] = combine(dp[i-1][j], dp[i][j-1], dp[i-1][j-1], cost(i, j));

Top-down memo (order-agnostic; best for sparse/complex transitions)

long long f(int i, int j, vector<vector<long long>>& memo) {
    if (base(i, j)) return baseVal;
    auto& res = memo[i][j];
    if (res != -1) return res;
    return res = /* transition over choices */;
}

1. Padding vs raw indexing: size (m+1)×(n+1) with row/col 0 as "empty prefix" removes every boundary if from LCS/edit-distance transitions. Use it by default for sequence DP; state the convention aloud.
2. Dependency-order bugs: interval DP iterated by l then r (instead of by length) reads uncomputed cells and fails quietly on some inputs. Derive the order from arrows: dp[l][r] needs shorter intervals ⇒ loop len = 2..n outermost.
3. Memo sentinel collisions: -1 as "uncomputed" breaks when −1 is a legal answer (game DP with negative scores) — use a separate seen array or LLONG_MIN.
4. O(n²) states × O(n) transition = O(n³): interval DP is usually cubic — say the complexity before coding so nobody expects magic; n ≤ ~500 is the constraint hint that cubic is intended.
5. Compressed-row aliasing: when collapsing to one row, dp[j-1] may be this row's value (new) while dp[j] is the last row's (old) — edit distance needs a saved prevDiag temp. If the juggling gets confusing in an interview, keep two rows: clarity > 2× memory.
6. Counting DPs overflow: paths/ways in a 2D grid explode combinatorially — long long or the problem's modulus from the first line, not after the WA.

What it is: Walk a grid moving only right/down: count the paths, or minimize the sum of visited cells. dp[i][j] = answer for reaching cell (i,j); the transition pulls from top and left.

Intuition: Movement restrictions (right/down only) make the grid a DAG — every cell's answer depends only on two already-computed neighbors, so one row-major sweep settles everything. Split-by-last-step again: any path into (i,j) arrived from above or from the left; counts add, costs min. Obstacles (63) just zero out cells. This is the 2D "hello world" — drill until the compressed one-row version is automatic.

Approach:

int minPathSum(vector<vector<int>>& g) {
    int m = g.size(), n = g[0].size();
    vector<int> dp(n, INT_MAX); dp[0] = 0;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) {
            if (j > 0) dp[j] = min(dp[j], dp[j-1]);   // dp[j] holds top (old), dp[j-1] left (new)
            dp[j] = (i || j) ? dp[j] + g[i][j] : g[0][0];
        }
    return dp[n-1];
}

1 3 1
1 5 1
4 2 1

What it is: Grid DP where the direction or the meaning twists: Dungeon Game (174) computes the minimum health needed — solvable only backwards from the princess; Maximal Square (221) redefines the state as a shape anchored at the cell — "the side of the largest square whose bottom-right corner is here."

Intuition: 174 teaches that the base case's location dictates the direction: "health needed at (i,j)" depends on where you're going, not where you've been — forward DP fails because future rooms can refund health (clamping breaks optimal substructure); backwards, need[i][j] = max(1, min(need[right], need[down]) − dungeon[i][j]) is clean. 221 teaches anchored-shape states: a square of side s at corner (i,j) requires squares of side s−1 at the three neighboring corners ⇒ dp[i][j] = 1 + min(top, left, topleft) — the min of three smaller shapes is the geometry.

Approach (221 core):

// dp[i][j] = side of largest all-1s square with bottom-right corner at (i,j)
if (g[i][j] == '1')
    dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
best = max(best, dp[i][j]);            // answer: best², recorded globally

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

What it is: Compare two sequences position by position: longest common subsequence, minimum edits to transform one into the other, counting distinct subsequence matches. dp[i][j] = answer for prefixes a[0..i) and b[0..j); the transition branches on whether a[i-1] == b[j-1].

Intuition: Split by what happens to the last characters: they match (consume both — a diagonal move) or one is skipped/edited (drop from a, drop from b, or substitute — the three edit-distance ops map exactly to the three neighbor cells: dp[i-1][j] = delete, dp[i][j-1] = insert, dp[i-1][j-1] = replace/match). Nearly every two-string problem is LCS or edit distance in costume — "min deletions to equalize" (583) = lengths − 2·LCS.

Approach:

int minDistance(string a, string b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; ++i) dp[i][0] = i;      // delete all of a's prefix
    for (int j = 0; j <= n; ++j) dp[0][j] = j;      // insert all of b's prefix
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            dp[i][j] = (a[i-1] == b[j-1])
                ? dp[i-1][j-1]
                : 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
    return dp[m][n];
}

What it is: Two-sequence DP where one side is a pattern with metacharacters: ?/. (any single char), * (wildcard: any sequence; regex: zero-or-more of the preceding element). dp[i][j] = "does s[0..i) match p[0..j)".

Intuition: Still last-decision partitioning, but * branches specially. Wildcard * (44): matches empty (dp[i][j-1]) or eats one more char and stays (dp[i-1][j]). Regex x* (10) is a unit: use zero copies (dp[i][j-2]) or, if x matches s[i-1], one more copy (dp[i-1][j]). The empty-pattern-prefix base row (dp[0][j]: only satisfied by chains of x* units) is half the marks.

Approach (10's transition, the part to memorize):

if (p[j-1] == '*')
    dp[i][j] = dp[i][j-2]                                        // zero copies of the unit
        || (i > 0 && matches(s[i-1], p[j-2]) && dp[i-1][j]);     // one more copy
else
    dp[i][j] = i > 0 && matches(s[i-1], p[j-1]) && dp[i-1][j-1];

What it is: Problems about palindromic subsequences (deletions allowed) inside one string: longest palindromic subsequence, min insertions to make the whole string a palindrome. State = a substring range (l, r); the transition compares the endpoints.

Intuition: Endpoints equal → they wrap a smaller problem: dp[l][r] = dp[l+1][r-1] + 2. Endpoints differ → one of them isn't in the optimal palindrome: max(dp[l+1][r], dp[l][r-1]). That two-case endpoint recursion is the whole family; 1312's cute reduction: min insertions = n − LPS(s), and LPS(s) itself = LCS(s, reverse(s)), tying Patterns 3 and 5 together. Subsequence here vs substring (5/647, expand-from-center) — deletions allowed vs contiguity, always route first.

Approach:

int longestPalindromeSubseq(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int l = n - 1; l >= 0; --l) {          // l descending, r ascending ⇒ deps ready
        dp[l][l] = 1;
        for (int r = l + 1; r < n; ++r)
            dp[l][r] = (s[l] == s[r]) ? dp[l+1][r-1] + 2
                                      : max(dp[l+1][r], dp[l][r-1]);
    }
    return dp[0][n-1];
}

What it is: An operation consumes elements of a range and its cost depends on what's around — burst balloons, cut a stick, triangulate a polygon. dp[l][r] = best for the open range (l, r); the transition picks which element acts last.

Intuition: The famous inversion: choosing the first balloon to burst entangles subproblems (its neighbors change for everything after). Choosing the last balloon k decouples them: when k finally bursts, its neighbors are exactly the range borders l and r — known! — and (l,k), (k,r) were solved independently before that. dp[l][r] = max over k of dp[l][k] + dp[k][r] + a[l]·a[k]·a[r]. "Think about the last decision, not the first" is the single transferable insight of interval DP.

Approach:

int maxCoins(vector<int>& nums) {
    vector<int> a = {1};                          // pad virtual 1s at both borders
    for (int x : nums) a.push_back(x);
    a.push_back(1);
    int n = a.size();
    vector<vector<int>> dp(n, vector<int>(n, 0)); // dp[l][r]: open interval (l, r)
    for (int len = 2; len < n; ++len)             // by increasing length — mandatory
        for (int l = 0; l + len < n; ++l) {
            int r = l + len;
            for (int k = l + 1; k < r; ++k)
                dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + a[l]*a[k]*a[r]);
        }
    return dp[0][n-1];
}

What it is: Knapsack with two budgets (474: strings cost zeros AND ones; capacity is m zeros, n ones) or counting ways to hit a target with grouped choices (1155: k dice, f faces, sum target). State = position + all remaining budgets.

Intuition: Each independent constraint is one dimension — 474 is literally 0/1 knapsack with a 2D capacity, compressed in place by iterating both budgets backwards. Dice counting (1155) shows the "grouped choices" shape: each die must contribute exactly one face — dp[d][t] = Σ_f dp[d-1][t-f] — a bounded, mandatory pick per stage (contrast: knapsack items are optional). Identifying optional-vs-mandatory and bounded-vs-unbounded per stage tells you which knapsack you're in.

Approach (474 core):

// dp[z][o] = max strings kept with z zeros and o ones of budget
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (auto& s : strs) {
    int z = count(s.begin(), s.end(), '0'), o = s.size() - z;
    for (int i = m; i >= z; --i)                  // both dims backwards: 0/1 semantics
        for (int j = n; j >= o; --j)
            dp[i][j] = max(dp[i][j], dp[i - z][j - o] + 1);
}
return dp[m][n];

What it is: The 1D file's state-machine pattern (hold/sold/rest) gains a counted resource: at most k buy-sell transactions. State = (day, transactions used, holding?) — the day axis rolls away, leaving a small 2D table updated per price.

Intuition: When a constraint is "at most k times," k becomes a dimension — the general rule for upgrading any state machine. The recurrences are buy[j] = max(buy[j], sell[j-1] − price) and sell[j] = max(sell[j], buy[j] + price). Special cases collapse: k=1 is 121, k=∞ is 122 (greedy), k=2 is 123 — and k ≥ n/2 is k=∞ (a transaction needs 2 days), the pruning that saves 188 from a huge k.

Approach (188, compact):

int maxProfit(int k, vector<int>& prices) {
    int n = prices.size();
    if (k >= n / 2) { /* unlimited: sum all positive deltas */ }
    vector<int> buy(k + 1, INT_MIN), sell(k + 1, 0);
    for (int p : prices)
        for (int j = 1; j <= k; ++j) {
            buy[j]  = max(buy[j],  sell[j-1] - p);
            sell[j] = max(sell[j], buy[j] + p);
        }
    return sell[k];
}

What it is: Two players alternate optimally — predict the winner or the final score difference. State = the remaining position (usually a range (l, r)); value = best score margin for whoever moves now.

Intuition: The "margin" formulation kills the two-player bookkeeping: dp[l][r] = max(a[l] − dp[l+1][r], a[r] − dp[l][r−1]) — take an end, minus the opponent's best margin on what remains (their gain is your loss; the negation is the turn switch). The first player wins iff dp[0][n-1] ≥ 0. For cost-guarantee games (375), the flip is max-over-adversary, min-over-you.

Approach:

// 486: dp[l][r] = current mover's best margin on a[l..r]
for (int l = n - 1; l >= 0; --l) {
    dp[l][l] = a[l];
    for (int r = l + 1; r < n; ++r)
        dp[l][r] = max(a[l] - dp[l+1][r], a[r] - dp[l][r-1]);
}
return dp[0][n-1] >= 0;

What it is: When "which items are already used" is unavoidable state and n ≤ ~20, encode the subset as an integer bitmask: dp[mask] (often dp[mask][last]). Assignment problems, minimum work sessions, visiting all nodes.

Intuition: 2ⁿ subsets fit in an int, and subset transitions are bit ops: add item i → mask | (1 << i); is i used → mask >> i & 1. The n ≤ 20 constraint in a problem statement is the pattern announcing itself. Two standard shapes: fill-by-subset (dp[mask] = best for exactly this set — iterate masks ascending) and BFS-over-masks when it's shortest-path-shaped (847: state = (node, visited-mask), plain BFS).

Approach (1986-style skeleton):

// dp[mask] = min sessions (and time used in the last session) covering tasks in mask
vector<pair<int,int>> dp(1 << n, {INT_MAX, INT_MAX});   // (sessions, lastSessionTime)
dp[0] = {1, 0};
for (int mask = 0; mask < (1 << n); ++mask)
    for (int i = 0; i < n; ++i) {
        if (mask >> i & 1) continue;
        auto [s, t] = dp[mask];
        int nm = mask | (1 << i);
        pair<int,int> cand = (t + task[i] <= T) ? make_pair(s, t + task[i])
                                                : make_pair(s + 1, task[i]);
        dp[nm] = min(dp[nm], cand);                     // lexicographic min works here
    }

What it is: Count structures by where the defining split happens: unique BSTs (96 — each value takes a turn as root, left/right counts multiply), ways to parenthesize an expression (241 — each operator takes a turn as the outermost split). dp[n] = Σ dp[i] · dp[n-1-i] — the Catalan convolution.

Intuition: When a structure has a distinguished top element (root, outermost operator, last-matched bracket pair), condition on it: the two sides become independent smaller instances, so counts multiply across the split and add across split choices. Recognize the convolution shape and you get 96, valid parenthesizations, triangulations, and full binary trees from one recurrence — Catalan numbers by any costume.

Approach:

int numTrees(int n) {
    vector<long long> dp(n + 1, 0); dp[0] = 1;      // empty tree: one way
    for (int nodes = 1; nodes <= n; ++nodes)
        for (int left = 0; left < nodes; ++left)
            dp[nodes] += dp[left] * dp[nodes - 1 - left];
    return dp[n];
}

What it is: Count numbers in [0, N] whose digits satisfy a property (contain only allowed digits, no consecutive ones, count of digit '1'). Walk N's digits left to right; state = (position, tight — "am I still glued to N's prefix?", plus property-specific state). Rare but unmistakable — nothing else looks like it.

Intuition: Every number ≤ N either shares N's prefix up to position i then uses a smaller digit (after which all remaining positions are free — count them combinatorially/memoized), or equals N's prefix entirely. The tight flag captures exactly this: tight ⇒ the current digit is capped at N's digit; not tight ⇒ 0–9 free and the memo applies (free states don't depend on N — that's why the memo works). Add a started flag when leading zeros matter.

Approach (skeleton):

// count numbers in [0, N] whose digits all belong to set D  (902-style)
long long f(int pos, bool tight, string& N, vector<long long>& memo /* non-tight only */) {
    if (pos == (int)N.size()) return 1;
    if (!tight && memo[pos] != -1) return memo[pos];
    long long res = 0;
    int cap = tight ? N[pos] - '0' : 9;
    for (int d = 0; d <= cap; ++d) {
        if (!allowed(d)) continue;
        res += f(pos + 1, tight && d == cap, N, memo);
    }
    if (!tight) memo[pos] = res;
    return res;
}