Longest Common Subsequence (LCS) — DP Classic

State

dp[i][j] = length of LCS of prefixes s1[0..i-1], s2[0..j-1].

State

dp[i][j] = length of LCS of prefixes s1[0..i-1], s2[0..j-1].

Transition

if (s1[i-1] == s2[j-1]) dp[i][j] = 1 + dp[i-1][j-1];
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

Reconstruction

Walk backward from dp[m][n]. Move up-left if match, up or left otherwise. Reconstructs the actual subsequence.

LCS vs LIS

LCS is 2D DP. Longest Increasing Subsequence is 1D. Related but different problems.