Longest Common Subsequence
Longest subsequence (order kept, gaps allowed) present in both strings text1 and text2.
Intuition
Compare the strings from the front, one prefix pair at a time. dp[i][j] = LCS of text1[:i] and text2[:j]. If the two current characters match, they surely end a common subsequence: 1 + the diagonal. If not, one of them is useless — drop either and take the better result. Every subproblem is a smaller prefix pair, so the table fills row by row.
Two strings, and a question about matching them up while preserving order — that's a 2-D grid DP where dp[i][j] answers the question for the first i and first j characters. The recurrence writes itself from one question: do the current two characters match? If yes, use them and step both back; if not, try dropping one from either side. Edit distance, shortest common supersequence and interleaving-string all fall out of the same frame.
Approach
Define the state
dp[i][j] = LCS length of the first i chars of text1 and first j chars of text2. dp[0][] = dp[][0] = 0 (empty prefix shares nothing).
The two-case transition
Match (text1[i-1]==text2[j-1]): dp[i][j] = dp[i-1][j-1] + 1. Mismatch: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) — best of skipping one char from either string.
Answer & backbone
dp[m][n] is the length. This exact table is the backbone of edit distance, diff tools, and many string DPs — worth knowing cold.
Solution & live demo
Common pitfalls
Sizing the table m × n instead of (m+1) × (n+1)
dp = [[0] * n for _ in range(m)]
dp = [[0] * (n + 1) for _ in range(m + 1)]
The extra row and column represent empty prefixes, and their zeros are the base case the whole recurrence leans on. Without them dp[i-1][j-1] falls off the grid at the first cell and you need special-cased branches everywhere.
Mixing up table indices and string indices
if text1[i] == text2[j]:
if text1[i-1] == text2[j-1]:
Because row i stands for the first i characters, the character it just added is at string position i - 1. Using i directly compares the wrong pair and runs off the end of the string on the last row.
Adding 1 in the mismatch branch
dp[i][j] = 1 + max(dp[i-1][j], dp[i][j-1])
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
The subsequence only grows when characters actually match. On a mismatch you're discarding one character and inheriting the best answer from a smaller problem — nothing was added to the common subsequence.
Edge cases
Table stays 0 everywhere — answer 0.
Row/column 0 base case handles it.
Diagonal fills 1,2,3,… — answer is the full length.