Dynamic Programming

Edit distance — also called Levenshtein distance — measures the minimum number of single-character insertions, deletions, or substitutions needed to turn one string into another. The classic dynamic-programming solution fills an (m+1)×(n+1) table where dp[i][j] is the cost to transform the first i characters of one string into the first j of the other. Each cell depends only on its top, left, and top-left neighbours, so the table fills row-by-row in O(m·n). The traceback through the dependencies reconstructs an optimal edit script. Variants underpin spell-checkers, DNA alignment, and diff tools.

The longest common subsequence (LCS) of two sequences is the longest sequence appearing in both as a subsequence — preserving order but not contiguity. The standard dynamic-programming solution fills an (m+1)×(n+1) table where dp[i][j] is the LCS length of the first i and j characters. When characters match, the cell extends the diagonal by one; otherwise it inherits the larger of its top and left neighbours. The table fills in O(m·n), and a traceback recovers the actual subsequence. LCS is the workhorse behind Unix `diff`, version control merge, and computational biology sequence alignment.