2D DP

Longest Common Subsequence

Compare two strings character by character. If s1[i] == s2[j], LCS here = 1 + dp[i−1][j−1]. Otherwise, LCS = max(dp[i−1][j], dp[i][j−1]) — try skipping a character from either string. Build the table bottom-up.

O(m*n)

How It Works

Longest Common Subsequence compares two strings with a 2D table where dp[i][j] is the LCS length of the first i characters of one string and the first j of the other. When the current characters match, they extend the best common subsequence of both shorter prefixes: dp[i][j] = 1 + dp[i-1][j-1]. When they differ, one of the two characters cannot be part of the answer, so dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

This fills m×n cells in O(mn) time, avoiding the 2^m subsequence enumeration of brute force. Two rows suffice for the length alone, though reconstructing the actual subsequence requires the full table to trace back through the choices. Edit Distance and many diff algorithms are direct relatives of this recurrence.

Step-by-Step Visualization

LCS of 'abcde' and 'ace'

s1abcde

s2ace

1/3

Code

Java

static int lcs(String s1, String s2) {
  int m = s1.length(), n = s2.length();
  int[][] dp = new int[m+1][n+1];

  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      dp[i][j] = s1.charAt(i-1) == s2.charAt(j-1)
        ? dp[i-1][j-1] + 1
        : Math.max(dp[i-1][j], dp[i][j-1]);

  return dp[m][n];
}
// lcs("abcde", "ace") → 3 ("ace")

Tips & Gotchas

1If chars match: dp[i][j] = dp[i-1][j-1] + 1

2If different: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3Backtrack through the table to reconstruct the LCS

Practice Problems

1Longest Common Subsequence
2Edit Distance
3Delete Operation for Two Strings
4Shortest Common Supersequence
5Uncrossed Lines

About the 2D DP Pattern

The state needs two variables — typically two indices (comparing two sequences), or a position in a grid. dp[i][j] depends on dp[i−1][j], dp[i][j−1], or dp[i−1][j−1]. Fills a 2D table.

Key insight

The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.

Common Dynamic Programming Interview Problems

Climbing Stairs
Coin Change
Longest Common Subsequence
0/1 Knapsack
Edit Distance
House Robber
Longest Increasing Subsequence
Word Break

Frequently Asked Questions

What distinguishes a subsequence problem from a substring problem?

Subsequences may skip characters, so mismatches carry information forward via max(dp[i-1][j], dp[i][j-1]). Longest Common Substring instead resets to 0 on mismatch because contiguity breaks. Confusing the two recurrences is a classic interview slip.

How does Edit Distance relate to LCS?

Both compare prefixes of two strings in a 2D table. Edit Distance adds a substitution option and minimizes operations — dp[i][j] = 1 + min(insert, delete, replace) on mismatch. For insert/delete-only costs, the answer is m + n - 2·LCS.

Can I recover the subsequence itself, not just its length?

Yes — keep the full table and walk from dp[m][n] backward: on a character match move diagonally and record the character, otherwise step toward the larger neighbor. The recorded characters, reversed, form one valid LCS.