Longest Common Subsequence

Various (Bellman era), 1953

Rooted in the dynamic programming work of the 1950s, the LCS algorithm builds a table where dp[i][j] holds the length of the longest common subsequence of the first i characters of one string and the first j characters of another. When characters match, the value comes from the diagonal; otherwise it takes the maximum of the cell above or to the left. A traceback from the bottom-right corner recovers the actual subsequence, shown here in coral.