Pattern Recognition Drill
Medium 2-D Dynamic Programming
The Problem
Given two strings, find the length of their longest common subsequence.
What approach would you use?
Think about it before scrolling down.
dp[i][j] = dp[i-1][j-1]+1 if match, else max(dp[i-1][j], dp[i][j-1]). O(mn).
Same 2D table. Can optimize to 1D with careful row management. O(mn) time, O(n) space.
Common Trap
This is subsequence, not substring — characters don't need to be consecutive.