LCS, edit distance, palindrome DP, and substring matching using 2D tables.
String DP problems typically build a 2D table dp[i][j] representing the answer for the first i characters of s1 and the first j characters of s2.
O(m × n)
O(m × n) reducible to O(n)
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
dp[i][j] = dp[i-1][j-1]+1 if match, else max(dp[i-1][j], dp[i][j-1])
dp[i][j] = 1 + min(insert, delete, replace)
LCS of s and reverse(s)
dp[i][j] = is substring i..j a palindrome
dp[i][j] counts ways to form t in s
dp[i][j] = can s1[:i] and s2[:j] interleave to form s3