2D Two-Sequence DP — DSA Pattern

🗂️

2D & Two-Sequence DP — LCS, Edit Distance, Grid DP

Build a 2D table where dp[i][j] uses dp[i-1][j-1] (match/replace), dp[i-1][j] (delete), dp[i][j-1] (insert).

Two-Sequence LCS Edit Distance Grid DP Time O(m·n) Space O(n) optimized

📋 When to Use

Two strings/sequences need cell-by-cell comparison
LCS: match → dp[i][j]=dp[i-1][j-1]+1; else max of top/left
Edit Distance: match → carry diagonal; else 1+min(D,I,R)
Grid DP: dp[i][j] = dp[i-1][j] + dp[i][j-1] (Unique Paths)
Palindrome via LCS: compare string vs its reverse

💡 Space optimization: each row only needs the previous row. Use a single 1D rolling array + one temp variable to get O(n) space from O(m·n).

⚡ Complexity

Time

O(m·n)

Space

O(n)*

*m = first string length (rows), n = second string length (cols). Full 2D table is O(m·n); rolling-row optimization gives O(min(m,n)).

Problem Given text1 = "ABCB" and text2 = "BCAB", find the length of their Longest Common Subsequence. If chars match → dp[i][j] = dp[i-1][j-1]+1; else → dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Input: text1="ABCB", text2="BCAB" · Answer: 3 — LCS is "BCB"

Step 0 / 16

dp[i][j] = LCS of text1[0..i-1] vs text2[0..j-1] | text1="ABCB" (rows), text2="BCAB" (cols)

cell

—

chars

—

result

—

LCS length

—

Press ▶ Play or Next ▶ to animate LCS table filling.

int[][] dp = new int[m+1][n+1];

Step 0 / 15

dp[i][j] = min ops to convert word1[0..i-1] to word2[0..j-1] | word1="horse" (rows), word2="ros" (cols)

cell

—

chars

—

operation

—

Edit Dist

—

Press ▶ Play or Next ▶ to animate Edit Distance table filling.

int[][] dp = new int[m+1][n+1];

Java Pattern Templates skeleton only

// ─── Longest Common Subsequence (2D DP) ─────────────────
int m = text1.length(), n = text2.length();
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (text1.charAt(i-1) == text2.charAt(j-1))
            dp[i][j] = dp[i-1][j-1] + 1;    // match: diagonal + 1
        else
            dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
    }
}
return dp[m][n];

// ─── Edit Distance (Insert / Delete / Replace) ───────────
int m = word1.length(), n = word2.length();
int[][] dp = new int[m+1][n+1];
for (int i = 0; i <= m; i++) dp[i][0] = i;   // i deletions
for (int j = 0; j <= n; j++) dp[0][j] = j;   // j insertions
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (word1.charAt(i-1) == word2.charAt(j-1))
            dp[i][j] = dp[i-1][j-1];              // no cost
        else
            dp[i][j] = 1 + Math.min(dp[i-1][j],    // delete
                           Math.min(dp[i][j-1],     // insert
                                    dp[i-1][j-1])); // replace
    }
}
return dp[m][n];

// ─── Unique Paths (Grid DP) ──────────────────────────────
int[] dp = new int[n];
Arrays.fill(dp, 1);                              // first row all 1
for (int i = 1; i < m; i++)
    for (int j = 1; j < n; j++)
        dp[j] += dp[j-1];                          // from-left + from-top
return dp[n-1];

🎯 Practice Problems

#1143 Longest Common Subsequence M #72 Edit Distance H #62 Unique Paths M #63 Unique Paths II M #120 Triangle M GFG Longest Common Substring M