Lessons from LCS

Three patterns to remember from LCS:

$1.$ Two sequences means 2D (two-dimensional) DP. Track progress in both with $dp[i][j]$.

$2.$ Match vs skip is the core decision. Match gives diagonal +1, skip gives max of top or left.

$3.$ Many problems reduce to LCS. "Minimum deletions to make strings equal" = $m + n - 2 \times LCS$. Next, you'll see Edit Distance, where you have three operations instead of just skip. Apply these patterns when you encounter similar problems.