2D / Sequence DP (LIS, LCS, Edit Distance)

Three classic problems -- Longest Common Subsequence, Longest Increasing Subsequence, and Edit Distance -- form the backbone of sequence-based dynamic programming. Master these and you unlock a huge family of contest problems where two strings, two arrays, or one sequence must be aligned, compared, or transformed optimally.

Difficulty: [Intermediate] Prerequisites: 1-D DP, Binary SearchCF Rating Range: 1400-1900

Quick Revisit
USE WHEN: comparing or aligning two sequences, or optimizing over subsequences
INVARIANT: dp[i][j] = answer for prefixes a[0..i-1] and b[0..j-1]
TIME: O(nm) for LCS/Edit Distance, O(n log n) for LIS | SPACE: O(nm), O(min(n,m)) rolling
CLASSIC BUG: confusing 0-indexed strings with 1-indexed DP table
PRACTICE: DP Practice Ladder

Intuition
LIS: O(n log n)
Edit Distance
STL / Language Features
Implementation
Complexity Analysis
Common Patterns & Variations
Debugging & Common Pitfalls
Cheat Sheet
Self-Test
Practice Problems
Further Reading

Contest Frequency: *** Common -- LIS/LCS appear regularly in Div 2 C/D

Intuition

You have two strings: $s =$ "ABCBDAB" and $t =$ "BDCAB". Find their Longest Common Subsequence (LCS).

Brute force: enumerate all $2^{7} = 128$ subsequences of $s$ , all $2^{5} = 32$ subsequences of $t$ , and check every pair. That is $O (2^{n} \cdot 2^{m})$ -- over 4 000 comparisons for this tiny input. For $n = m = 1000$ , the universe ends before you finish.

There has to be a better way.

The answer for prefixes $s [0. . i]$ and $t [0. . j]$ depends only on shorter prefixes -- so $d p [i] [j]$ captures everything we need.

Think of it like filling a grid from the top-left corner. The base case is "empty string vs. empty string" at $(0, 0)$ . Each cell $(i, j)$ only looks at its neighbors above, to the left, and diagonally up-left. By the time you reach the bottom-right corner, you have your answer.

This is the 2D DP pattern: two indices scan two sequences, and each state depends on a constant number of smaller states.

Visual Walkthrough -- LCS of "ABCBDAB" and "BDCAB"

Build $d p [i] [j]$ = length of LCS of $s [0. . i - 1]$ and $t [0. . j - 1]$ .

Rule: If $s [i - 1] = t [j - 1]$ , take the diagonal + 1. Otherwise, take max of the cell above and the cell to the left.

Filling direction -- row by row, left to right:

  Scan order:     Why it works -- each cell's 3 inputs
                  are already computed:
  ──->──->──->──->
  ──->──->──->──->       ↖ (i-1,j-1)  ↑ (i-1,j)
  ──->──->──->──->             ╲       │
  ──->──->──->──->       <- (i,j-1) ──-> (i,j)
  ──->──->──->──->
                    ↖ = previous row, earlier col  OK done
  (top to bottom,   ↑ = previous row, same col    OK done
   left to right)   <- = same row, earlier col     OK done

Step 1 -- Base cases (row 0 and column 0 are all zeros):

            ""  B  D  C  A  B
       ""    0  0  0  0  0  0
        A    0  .  .  .  .  .
        B    0  .  .  .  .  .
        C    0  .  .  .  .  .
        B    0  .  .  .  .  .
        D    0  .  .  .  .  .
        A    0  .  .  .  .  .
        B    0  .  .  .  .  .

Step 2 -- Fill row 1 ( $s [0]$ = 'A'):

'A' does not match 'B','D','C', so copy max of neighbors. Matches 'A' at column 4: diagonal(0)+1 = 1. Then 1 carries right.

            ""  B  D  C  A  B
       ""    0  0  0  0  0  0
        A    0  0  0  0  1  1

Step 3 -- Fill row 2 ( $s [1]$ = 'B'):

'B' matches $t [0]$ = 'B': diagonal(0)+1 = 1. No more matches until column 5 where 'B' matches again: diagonal(1)+1 = 2.

        B    0  1  1  1  1  2

Step 4 -- Fill rows 3-5:

        C    0  1  1  2  2  2     <-- C matches t[2]='C'
        B    0  1  1  2  2  3     <-- B matches t[4]='B', diag 2+1=3
        D    0  1  2  2  2  3     <-- D matches t[1]='D'

Step 5 -- Fill rows 6-7:

        A    0  1  2  2  3  3     <-- A matches t[3]='A', diag 2+1=3
        B    0  1  2  2  3  4     <-- B matches t[4]='B', diag 3+1=4

Complete table:

            ""  B  D  C  A  B
       ""    0  0  0  0  0  0
        A    0  0  0  0  1  1
        B    0  1  1  1  1  2
        C    0  1  1  2  2  2
        B    0  1  1  2  2  3
        D    0  1  2  2  2  3
        A    0  1  2  2  3  3
        B    0  1  2  2  3  4

Answer: $d p [7] [5] = 4$ .

Traceback -- walk from $(7, 5)$ backwards. At each match (diagonal move), record the character:

  (7,5) B=B  -> diagonal to (6,4)   record 'B'
  (6,4) A=A  -> diagonal to (5,3)   record 'A'
  (5,3) D!=C -> up to (4,3)
  (4,3) B!=C -> up to (3,3)
  (3,3) C=C  -> diagonal to (2,2)   record 'C'
  (2,2) B!=D -> left to (2,1)
  (2,1) B=B  -> diagonal to (1,0)   record 'B'
  Done.

Read recorded characters in reverse: "BCAB" -- a longest common subsequence of length 4.

The Invariant

$d p [i] [j]$ = length of the LCS of $s [0. . i - 1]$ and $t [0. . j - 1]$ .
Fill order: row by row, left to right (or column by column).
Recurrence:
If $s [i - 1] = t [j - 1]$ : $d p [i] [j] = d p [i - 1] [j - 1] + 1$
Else: $d p [i] [j] = max (d p [i - 1] [j], d p [i] [j - 1])$
Traceback: diagonal arrow = match (record the character); otherwise follow the larger neighbor.

What the Code Won't Teach You

The hidden LCS / edit-distance duality. If the LCS of two strings of lengths $n$ and $m$ has length $k$ , then the edit distance using only insert and delete (no replace) is exactly $n + m - 2 k$ . Why? You delete the $n - k$ characters of $s$ not in the LCS, then insert the $m - k$ characters of $t$ not in the LCS. This means solving LCS instantly gives you a delete/insert-only edit distance, and vice versa. Many contest problems exploit this link.

When space optimization breaks. The rolling-array trick (Section 6.2) reduces memory from $O (n m)$ to $O (min (n, m))$ -- but it destroys the full table you need for backtrace reconstruction. If a problem asks for the actual subsequence or alignment (not just the length/cost), you must keep the entire table, or use the more complex Hirschberg divide-and-conquer algorithm that achieves $O (min (n, m))$ space with reconstruction.

Affine gap penalties. In bioinformatics-style alignment the cost of a gap (consecutive insertions or deletions) is not simply $k \times d$ . Instead it follows an affine model: opening a gap costs $g_{o}$ and extending it costs $g_{e}$ per character ( $g_{e} < g_{o}$ ). This requires splitting the DP state into three tables -- "match/mismatch", "gap in $s$ ", "gap in $t$ " -- but the same 2D prefix structure applies. Contest problems occasionally use this model (look for "gap open / gap extend" in the statement).

When to Reach for This

Trigger phrases in problem statements:

Phrase	Likely model
"longest common subsequence"	LCS
"edit distance" / "minimum operations to transform"	Edit distance
"longest increasing subsequence"	LIS
"align two sequences"	2D DP on prefixes
"insert, delete, replace"	Edit distance variant
"minimum number of deletions to make equal"	LCS (answer = $n + m - 2 \cdot LCS$ )

Counter-examples (look similar but aren't 2D sequence DP):

"Longest common substring" -- sliding window + hashing or suffix structures, not subsequence DP.
"Shortest common supersequence" -- builds on LCS but needs additional reconstruction logic.
"Number of distinct subsequences" -- counting DP with a different recurrence.

LCS and edit distance cover the two-sequence case. A closely related single-sequence problem -- finding the longest increasing subsequence -- appears just as often in contests and benefits from a faster algorithm.

LIS: $O (n \log n)$ via Patience Sorting

The Longest Increasing Subsequence deserves special treatment because the naive $O (n^{2})$ DP is too slow for $n \leq 10^{5}$ (common in contests). The key idea: maintain an array tails where tails[k] is the smallest tail element of any increasing subsequence of length $k + 1$ seen so far.

Example: $a = [3, 1, 4, 1, 5, 9, 2, 6]$

  Process 3 : tails = [3]
  Process 1 : 1 < 3, replace      -> tails = [1]
  Process 4 : 4 > 1, append       -> tails = [1, 4]
  Process 1 : 1 <= 1, no change   -> tails = [1, 4]
  Process 5 : 5 > 4, append       -> tails = [1, 4, 5]
  Process 9 : 9 > 5, append       -> tails = [1, 4, 5, 9]
  Process 2 : replace 4 at pos 1  -> tails = [1, 2, 5, 9]
  Process 6 : replace 9 at pos 3  -> tails = [1, 2, 5, 6]

LIS length = 4. (Note: tails itself is not a valid LIS -- it is a bookkeeping structure. See Section 6.3 for full recovery.)

Each step does one binary search -> $O (\log n)$ per element -> $O (n \log n)$ total.

Why it works: tails is always sorted. Replacing a value with a smaller one can never hurt -- it only opens up more room for future elements to extend a subsequence.

LIS optimizes a single sequence. The next classic 2D problem -- edit distance -- returns to the two-sequence setting but replaces "find a common part" with "transform one into the other."

Edit Distance

Transform string $s$ into string $t$ using the minimum number of single-character operations: insert, delete, or replace (each costs 1).

$d p [i] [j]$ = edit distance between $s [0. . i - 1]$ and $t [0. . j - 1]$ .

Recurrence:

If $s [i - 1] = t [j - 1]$ : $d p [i] [j] = d p [i - 1] [j - 1]$ (no cost)
Else: $d p [i] [j] = 1 + min (d p [i - 1] [j], d p [i] [j - 1], d p [i - 1] [j - 1])$
- $d p [i - 1] [j] + 1$ : delete $s [i - 1]$
- $d p [i] [j - 1] + 1$ : insert $t [j - 1]$
- $d p [i - 1] [j - 1] + 1$ : replace $s [i - 1]$ with $t [j - 1]$

Base cases: $d p [i] [0] = i$ (delete everything), $d p [0] [j] = j$ (insert everything).

Quick example -- "cat" -> "cut":

            ""  c  u  t
       ""    0  1  2  3
        c    0  0  1  2
        a    0  1  1  2
        t    0  2  2  1

Answer: 1 (replace 'a' with 'u').

Operation trace -- which operation produced each cell:

              ""      c       u       t
  ""        [ 0 ] -> 1:I   -> 2:I   -> 3:I        -> = insert (from left)
              ↓      ↘       ↓       ↓
   c        1:D    [ 0:= ] -> 1:I   -> 2:I        ↓ = delete (from above)
              ↓      ↓       ↘       ↓
   a        2:D     1:D    [ 1:R ] -> 2:I        ↘ = match (free) or replace
              ↓      ↓       ↓       ↘
   t        3:D     2:D     2:D    [ 1:= ]      D=delete  I=insert  R=replace  ==match

  Optimal path [ ]: (0,0)↘(1,1)↘(2,2)↘(3,3)
    = match 'c' (free) + replace 'a'->'u' (cost 1) + match 't' (free)
    = total cost 1

3. STL / Language Features Used

Feature	Header	Purpose
`vector<vector<int>>`	`<vector>`	2D DP table
`string`	`<string>`	Input sequences
`lower_bound` / `upper_bound`	`<algorithm>`	Binary search in LIS
`min`, `max`	`<algorithm>`	Recurrence transitions
`ranges::reverse`	`<algorithm>`	Reverse traceback string
`min({a, b, c})`	`<algorithm>`	3-way min with initializer list

Implementation

LCS -- Length and Reconstruction

cpp

#include <bits/stdc++.h>
using namespace std;

// Returns the LCS string (not just its length).
string lcs(const string& s, const string& t) {
    int n = s.size(), m = t.size();
    vector dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }

    // Traceback: walk from (n, m) to (0, 0).
    string res;
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (s[i - 1] == t[j - 1]) {
            res += s[i - 1];
            i--; j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    ranges::reverse(res);
    return res;
}

int main() {
    string s, t;
    cin >> s >> t;
    string ans = lcs(s, t);
    cout << ans.size() << "\n" << ans << "\n";
}

LIS -- $O (n \log n)$

cpp

#include <bits/stdc++.h>
using namespace std;

// Returns length of the longest *strictly* increasing subsequence.
int lis(const vector<int>& a) {
    vector<int> tails;
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end())
            tails.push_back(x);
        else
            *it = x;
    }
    return tails.size();
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    cout << lis(a) << "\n";
}

Strictly vs. non-strictly increasing: For non-decreasing ( $\leq$ ), use upper_bound instead of lower_bound.

Edit Distance

cpp

#include <bits/stdc++.h>
using namespace std;

int edit_distance(const string& s, const string& t) {
    int n = s.size(), m = t.size();
    vector dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[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[n][m];
}

int main() {
    string s, t;
    cin >> s >> t;
    cout << edit_distance(s, t) << "\n";
}

Complexity Analysis

Before submitting, check that your chosen algorithm fits the problem's constraints. The table below maps each variant to its time and space costs.

Algorithm	Time	Space	Notes
LCS (basic)	$O (n m)$	$O (n m)$	$n, m$ = string lengths
LCS (space-optimized)	$O (n m)$	$O (min (n, m))$	Keep only 2 rows
LIS (binary search)	$O (n \log n)$	$O (n)$	Optimal for $n \leq 10^{6}$
LIS (naive DP)	$O (n^{2})$	$O (n)$	Only if $n \leq 5000$
Edit distance	$O (n m)$	$O (n m)$	Same grid structure as LCS
Edit distance (space-opt)	$O (n m)$	$O (min (n, m))$	2-row rolling trick

Rule of thumb: $O (n m)$ passes when $n \cdot m \leq 2.5 \times 10^{7}$ (roughly 1-2 seconds in C++). Typical contest limits that signal this approach: $n, m \leq 5000$ . If $n$ or $m$ exceeds $10^{5}$ , you need a specialized algorithm (Hunt-Szymanski, bit-parallel LCS, etc.).

6. Common Patterns & Variations

6.1 Printing the Actual LCS

You need the full $O (n m)$ table -- no space optimization. Walk backwards from $d p [n] [m]$ (see implementation above). If both directions are tied ( $d p [i - 1] [j] = d p [i] [j - 1]$ ), either choice gives a valid LCS (though not necessarily the same one).

6.2 Space Optimization to $O (min (n, m))$

If you only need the length, keep two rows: prev and curr.

cpp

int lcs_length(const string& s, const string& t) {
    int n = s.size(), m = t.size();
    if (n < m) return lcs_length(t, s); // ensure m is the smaller dim
    vector<int> prev(m + 1, 0), curr(m + 1, 0);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1])
                curr[j] = prev[j - 1] + 1;
            else
                curr[j] = max(prev[j], curr[j - 1]);
        }
        swap(prev, curr);
        fill(curr.begin(), curr.end(), 0);
    }
    return prev[m];
}

Same trick works for edit distance -- just be careful with the diagonal value (save prev[j-1] before overwriting it).

Rolling array -- how two rows replace the full table:

  Full table (O(nm) space):          Rolling array (O(m) space):

  ┌─────┬─────┬─────┬─────┐        After processing row i-1:
  │(0,0)│(0,1)│(0,2)│(0,3)│          prev[]: [dp(i-1,0)] [dp(i-1,1)] [dp(i-1,2)] [dp(i-1,3)]
  ├─────┼─────┼─────┼─────┤          curr[]: [    ?     ] [    ?     ] [    ?     ] [    ?     ]
  │(1,0)│(1,1)│(1,2)│(1,3)│
  ├─────┼─────┼─────┼─────┤        While filling curr[j] for row i:
  │(2,0)│(2,1)│(2,2)│(2,3)│          prev[j-1] = ↖ diagonal    <- from previous row
  ├─────┼─────┼─────┼─────┤          prev[j]   = ↑ above        <- from previous row
  │(3,0)│(3,1)│(3,2)│(3,3)│          curr[j-1] = <- left         <- just computed this row
  └─────┴─────┴─────┴─────┘
                                    After row i is done:
  Rows 0..i-2 are never                swap(prev, curr);  // prev <- row i
  read again once row i                fill(curr, 0);     // curr <- ready for i+1
  is being filled.

⚠️ Reconstruction is lost: with only two rows, you cannot trace back through the full table -- the earlier rows are gone. If you need the actual LCS string (not just its length), keep the entire table or use Hirschberg's algorithm.

6.3 Recovering the Actual LIS

The tails array does not contain a valid LIS. To reconstruct, store predecessor links and the position each element was placed at:

cpp

pair<int, vector<int>> lis_with_recovery(const vector<int>& a) {
    int n = a.size();
    vector<int> tails, tail_idx; // tail_idx[k] = index in a[] at pos k
    vector<int> pos(n), parent(n, -1);

    for (int i = 0; i < n; i++) {
        int p = lower_bound(tails.begin(), tails.end(), a[i])
                - tails.begin();
        if (p == (int)tails.size()) {
            tails.push_back(a[i]);
            tail_idx.push_back(i);
        } else {
            tails[p] = a[i];
            tail_idx[p] = i;
        }
        pos[i] = p;
        if (p > 0) parent[i] = tail_idx[p - 1];
    }

    int len = tails.size();
    vector<int> result(len);
    int k = tail_idx[len - 1];
    for (int i = len - 1; i >= 0; i--) {
        result[i] = a[k];
        k = parent[k];
    }
    return {len, result};
}

6.4 Non-Decreasing LIS

Replace lower_bound with upper_bound. This allows equal consecutive elements (e.g., $[1, 2, 2, 3]$ is a valid non-decreasing subsequence).

6.5 Weighted Edit Distance

Replace the fixed cost of 1 with arbitrary per-operation weights. The recurrence structure is identical:

dp[i][j] = min(
    dp[i-1][j]   + cost_delete,
    dp[i][j-1]   + cost_insert,
    dp[i-1][j-1] + (s[i-1] == t[j-1] ? 0 : cost_replace)
);

Some problems assign different costs per character -- just index into a cost table.

6.6 LCS of Permutations -> LIS

If both sequences are permutations of ${1, \dots, n}$ , map one to the identity (position array) and apply the same mapping to the other. The LCS reduces to LIS on the mapped sequence -- solvable in $O (n \log n)$ instead of $O (n^{2})$ .

6.7 Minimum Deletions to Make Two Strings Equal

This is LCS in disguise. Delete characters from both strings until they match. Answer = $n + m - 2 \cdot LCS (s, t)$ .

7. Debugging & Common Pitfalls

Pitfall	Symptom	Fix
Off-by-one on indices	WA on small cases	Table is $(n + 1) \times (m + 1)$ ; strings are 0-indexed
Forgetting base cases	Garbage in row/column 0	`dp[i][0] = i`, `dp[0][j] = j` for edit distance
Strict vs. non-strict LIS	Length off by 1-2	`lower_bound` = strict, `upper_bound` = non-decreasing
Traceback direction	Reversed or wrong LCS	Build string backwards, reverse at the end
MLE on large inputs	$n = m = 10^{4}$ with full table	Use 2-row optimization if traceback not needed
Not handling empty strings	RE or WA	Base row and column cover this; make sure loops start at 1

Debugging tip: For small inputs, print the entire DP table. A wrong cell is immediately visible when you verify the recurrence by hand. Example debug output:

  dp table for s="AB", t="BA":
      ""  B  A
  ""   0  0  0
   A   0  0  1
   B   0  1  1

If any cell doesn't satisfy the recurrence, you have a bug.

Mental Traps

Trap 1: "LCS and edit distance are the same algorithm."

They share the same 2D DP grid shape and both iterate over string prefixes, but they optimize different objectives. LCS maximizes matches; edit distance minimizes operations. The diagonal transition means opposite things: in LCS a match adds +1, in edit distance a match adds +0 (free). Confusing them leads to using max where you need min, or forgetting the base-case difference (dp[i][0] = 0 for LCS vs. dp[i][0] = i for edit distance).

Trap 2: "I can recover the LCS just from dp[n][m]."

dp[n][m] only stores the length. To reconstruct the actual subsequence you need the entire table so you can trace back from (n,m) to (0,0), following diagonal arrows on matches. This is exactly why the 2-row space optimization (Section 6.2) is incompatible with reconstruction -- it throws away the rows you need for the backtrace.

Trap 3: "The order of iteration doesn't matter as long as i and j increase."

It does matter. Each cell depends on three specific neighbors:

  Dependency arrows in dp[i][j]:

    dp[i-1][j-1] ──-> dp[i-1][j]
         │ ╲              │
         ↓   ╲            ↓
    dp[i][j-1] ──-> dp[i][j]

  Each cell needs: ↑ above, <- left, ↖ diagonal
  Valid fill orders: row-by-row L->R, col-by-col T->B
  INVALID: random order, reverse row, bottom-up R->L

If you fill right-to-left within a row, dp[i][j-1] hasn't been computed yet when you need it. If you fill bottom-to-top, dp[i-1][j] is stale. The dependency arrows dictate that row-by-row left-to-right (or column-by-column top-to-bottom) are the only valid orders.

8. Cheat Sheet

+-------------------------------------------------------------------+
|                    2D / SEQUENCE DP                                |
+-------------------------------------------------------------------+
| LCS(s, t):                                                        |
|   dp[i][j] = LCS length of s[0..i-1], t[0..j-1]                 |
|   match:     dp[i][j] = dp[i-1][j-1] + 1                        |
|   mismatch:  dp[i][j] = max(dp[i-1][j], dp[i][j-1])             |
|   Answer:    dp[n][m]           Time: O(nm)  Space: O(nm)         |
+-------------------------------------------------------------------+
| Edit Distance(s, t):                                              |
|   dp[i][j] = min ops to turn s[0..i-1] into t[0..j-1]           |
|   match:     dp[i][j] = dp[i-1][j-1]                             |
|   mismatch:  dp[i][j] = 1 + min(up, left, diag)                  |
|   Base:      dp[i][0] = i,  dp[0][j] = j                         |
|   Answer:    dp[n][m]           Time: O(nm)  Space: O(nm)         |
+-------------------------------------------------------------------+
| LIS  (O(n log n)):                                                |
|   tails[] = smallest tail of IS of each length                    |
|   For each x:  pos = lower_bound(tails, x)                       |
|     pos == end ? append : replace                                 |
|   Answer:    tails.size()       Time: O(n log n)  Space: O(n)     |
|   Strict: lower_bound  |  Non-decreasing: upper_bound             |
+-------------------------------------------------------------------+
| Quick formulas:                                                   |
|   Min deletions to equalize = n + m - 2 * LCS(s, t)              |
|   SCS length               = n + m - LCS(s, t)                   |
|   LCS of two permutations  = LIS of the mapped sequence          |
+-------------------------------------------------------------------+

Common Mistakes

0-indexed vs 1-indexed confusion. C++ strings are 0-indexed, but the DP table is typically 1-indexed (row 0 / col 0 = empty prefix). Off-by-one here corrupts every cell.
Wrong LIS comparison operator. Use strict < for strictly increasing, <= for non-decreasing. Swapping these changes the answer.
Forgetting the diagonal in LCS. When characters match, the transition is dp[i-1][j-1] + 1, not max(dp[i-1][j], dp[i][j-1]).
Rolling array direction. When reducing to one row, you must process the inner loop in the right direction to avoid overwriting values you still need.
Printing the actual subsequence. Backtracking through the DP table requires the full 2D array -- space optimization breaks reconstruction.
LCS swapping match and mismatch branches. Writing dp[i-1][j-1] + 1 in the mismatch branch instead of the match branch silently reports length 0 for overlapping strings. Always write the recurrence on paper first, label each case explicitly (match vs mismatch), then translate to code.

Debug Drills

Drill 1. LCS returns a length longer than both input strings.

cpp

int dp[1001][1001] = {};
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (a[i] == b[j])
            dp[i][j] = dp[i-1][j-1] + 1;
        else
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + 1;

What's wrong?

The + 1 in the else branch is wrong. On a mismatch, you should just take the max of the two subproblems without adding anything: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). The + 1 only belongs in the match branch.

Drill 2. Edit distance gives 0 for transforming "abc" into "" (empty string).

cpp

int dp[1001][1001];
for (int i = 0; i <= n; i++)
    for (int j = 0; j <= m; j++) {
        if (i == 0 && j == 0) dp[i][j] = 0;
        else if (a[i] == b[j]) 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]});
    }

What's wrong?

Base cases are missing: when i == 0, dp[0][j] should be j (insert all); when j == 0, dp[i][0] should be i (delete all). Without these, the first row and column are 0, making the answer wrong.

Drill 3. $O (n \log n)$ LIS returns the wrong subsequence elements.

cpp

vector<int> tails;
for (int x : a) {
    auto it = lower_bound(tails.begin(), tails.end(), x);
    if (it == tails.end()) tails.push_back(x);
    else *it = x;
}
// tails is the LIS?

What's wrong?

The tails array does NOT contain the actual LIS -- it only has the correct length. The values in tails are a mix of elements from different subsequences. To reconstruct the actual LIS, maintain a separate parent[] / pos[] array tracking where each element was placed, then backtrack.

Self-Test

[ ] Write the LCS recurrence from memory, including correct base cases
[ ] Write the edit distance recurrence with all 3 operations explicit
[ ] Implement LCS backtrace to recover the actual subsequence string
[ ] Explain why rolling-array LCS cannot support reconstruction
[ ] Derive: min deletions to equalize two strings = n + m - 2*LCS
[ ] State when to use lower_bound vs upper_bound in patience sorting LIS

Bug Gallery

Bug 1: LCS -- using 0-indexed strings with 1-indexed DP without offset

cpp

string a, b;
cin >> a >> b;
int n = a.size(), m = b.size();
int dp[1001][1001] = {};
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (a[i] == b[j])  // ❌ Bug: a and b are 0-indexed
            dp[i][j] = dp[i-1][j-1] + 1;
        else
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

Why it's wrong: C++ strings are 0-indexed, so a[i] when i starts at 1 is off by one. a[n] accesses past the end of the string.

Fix:

cpp

if (a[i-1] == b[j-1])  // ✅ Offset by 1 for 0-indexed strings

Bug 2: Edit distance -- forgetting to handle the match case (no-op)

cpp

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});  // ❌ Bug

Why it's wrong: When a[i-1] == b[j-1], the characters match and no operation is needed -- dp[i][j] should inherit dp[i-1][j-1] without the +1. This code always adds 1, overcounting the edit distance.

Fix:

cpp

if (a[i-1] == b[j-1])
    dp[i][j] = dp[i-1][j-1];  // ✅ No cost for matching characters
else
    dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});

Bug 3: LIS -- using upper_bound instead of lower_bound for strictly increasing

cpp

vector<int> tails;
for (int x : a) {
    auto it = upper_bound(tails.begin(), tails.end(), x);  // ❌ Bug
    if (it == tails.end()) tails.push_back(x);
    else *it = x;
}

Why it's wrong: upper_bound finds the first element strictly greater than x. This allows equal elements in tails, producing a longest non-decreasing subsequence instead of strictly increasing. For strict LIS, use lower_bound (first element >= x).

Fix:

cpp

auto it = lower_bound(tails.begin(), tails.end(), x);  // ✅ Strictly increasing

Bug 4: Wrong LCS base case -- not initializing dp[0][j] and dp[i][0] to 0

cpp

int dp[1001][1001];
// No initialization ❌ Bug
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (a[i-1] == b[j-1])
            dp[i][j] = dp[i-1][j-1] + 1;
        else
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

Why it's wrong: The recurrence reads dp[0][j] and dp[i][0], which represent the LCS of any string with an empty string -- always 0. Without initialization, these contain garbage values, producing nonsensical results. Using = {} or memset(dp, 0, sizeof dp) is mandatory.

Fix:

cpp

int dp[1001][1001] = {};  // ✅ All base cases dp[0][j] = dp[i][0] = 0

Bug 5: LIS -- using lower_bound when non-decreasing subsequence is needed

cpp

// Want longest NON-DECREASING subsequence
vector<int> tails;
for (int x : a) {
    auto it = lower_bound(tails.begin(), tails.end(), x);  // ❌ Bug
    if (it == tails.end()) tails.push_back(x);
    else *it = x;
}

Why it's wrong: lower_bound finds the first element >= x, which replaces equal elements and enforces strict increase. For a non-decreasing subsequence (allowing duplicates), use upper_bound (first element > x) so that equal values extend the subsequence rather than replacing existing entries.

Fix:

cpp

auto it = upper_bound(tails.begin(), tails.end(), x);  // ✅ Non-decreasing

Bug 6: Edit distance -- using wrong diagonal cell on character match

cpp

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
        dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
        if (a[i-1] == b[j-1])
            dp[i][j] = min(dp[i][j], dp[i][j-1]);  // ❌ Bug: wrong cell
    }

Why it's wrong: When characters match, the edit distance should inherit from the diagonal dp[i-1][j-1] (both strings advanced by one with no operation). Using dp[i][j-1] is the deletion/insertion transition, not the match transition, giving wrong results.

Fix:

cpp

if (a[i-1] == b[j-1])
    dp[i][j] = min(dp[i][j], dp[i-1][j-1]);  // ✅ Diagonal = match/no-op

Practice Problems

CF Rating	How 2D Sequence DP Appears
1200	Basic LCS, edit distance with unit costs
1500	LIS with $O (n \log n)$ , DP on grid paths, string alignment with custom costs
1800	LCS on permutations (reduce to LIS), edit distance with non-trivial operations
2100	Hirschberg's space optimization, LCS + bitmask speedup, Hunt-Szymanski

#	Problem	Key Idea	Link
1	CSES -- Increasing Subsequence	LIS, $O (n \log n)$ required ( $n \leq 2 \times 10^{5}$ )	cses.fi/problemset/task/1145
2	CSES -- Edit Distance	Textbook edit distance	cses.fi/problemset/task/1639
3	AtCoder DP Contest -- F (LCS)	LCS with reconstruction	atcoder.jp/contests/dp/tasks/dp_f
4	Codeforces 340D -- Bubble Sort Graph	LIS in disguise (max independent set = LIS)	codeforces.com/problemset/problem/340/D
5	AtCoder DP Contest -- Q (Flowers)	LIS variant with weights	atcoder.jp/contests/dp/tasks/dp_q

Progression: Start with problems 1-3 (direct application). Move to 4-5 once you can spot the reduction to LIS/LCS in a non-obvious setting.

Recap

LCS: 2D table, match diagonally, skip along edges. O(nm) time.
LIS: patience sorting with lower_bound. O(n log n) time. The tails array length is the LIS length.
Edit distance: 2D table with insert / delete / replace transitions. O(nm) time.
Space optimization: rolling array reduces space from O(nm) to O(min(n,m)), but loses backtracking ability.

Cross-Links

DP -- 1D Introduction -- master 1D DP before adding a second dimension
DP Thinking Framework -- systematic state design for sequence DP variants
DP vs Greedy Guide -- LIS has a greedy-flavored O(n log n) algorithm
DP Practice Ladder -- graded problem set

2D / Sequence DP (LIS, LCS, Edit Distance) ​

Contents ​

Intuition ​

Visual Walkthrough -- LCS of "ABCBDAB" and "BDCAB" ​

The Invariant ​

What the Code Won't Teach You ​

When to Reach for This ​

LIS: O(nlog⁡n) via Patience Sorting ​

Edit Distance ​

3. STL / Language Features Used ​

Implementation ​

LCS -- Length and Reconstruction ​

LIS -- O(nlog⁡n) ​

Edit Distance ​

Complexity Analysis ​

6. Common Patterns & Variations ​

6.1 Printing the Actual LCS ​

6.2 Space Optimization to O(min(n,m)) ​

6.3 Recovering the Actual LIS ​

6.4 Non-Decreasing LIS ​

6.5 Weighted Edit Distance ​

6.6 LCS of Permutations -> LIS ​

6.7 Minimum Deletions to Make Two Strings Equal ​

7. Debugging & Common Pitfalls ​

Mental Traps ​

8. Cheat Sheet ​

Common Mistakes ​

Debug Drills ​

Self-Test ​

Bug Gallery ​

Practice Problems ​

Further Reading ​

Related Techniques ​

Recap ​

Cross-Links ​

2D / Sequence DP (LIS, LCS, Edit Distance)

Contents

Intuition

Visual Walkthrough -- LCS of "ABCBDAB" and "BDCAB"

The Invariant

What the Code Won't Teach You

When to Reach for This

LIS: $O (n \log n)$ via Patience Sorting

Edit Distance

3. STL / Language Features Used

Implementation

LCS -- Length and Reconstruction

LIS -- $O (n \log n)$

Edit Distance

Complexity Analysis

6. Common Patterns & Variations

6.1 Printing the Actual LCS

6.2 Space Optimization to $O (min (n, m))$

6.3 Recovering the Actual LIS

6.4 Non-Decreasing LIS

6.5 Weighted Edit Distance

6.6 LCS of Permutations -> LIS

6.7 Minimum Deletions to Make Two Strings Equal

7. Debugging & Common Pitfalls

Mental Traps

8. Cheat Sheet

Common Mistakes

Debug Drills

Self-Test

Bug Gallery

Practice Problems

Further Reading

Related Techniques

Recap

Cross-Links