最長共同子序列（longest common subsequence, LCS）

一個字串的子序列，是你刪掉它某些字元（可能一個都不刪）而不重排其餘所得到的——所以 'ace' 是 'abcde' 的子序列，但 'aec' 不是，因為順序必須保留。兩個字串的最長共同子序列，是同時為兩者子序列的最長字串。它衡量兩個序列以相同順序共享了多少，這正是它撐起比對檔案版本的 diff 工具、拼字檢查建議、甚至生物學中 DNA 比對的原因。

這個動態規劃的關鍵在於觀察最後一個字元。令 dp[i][j] 為字串 A 前 i 個字元與字串 B 前 j 個字元的最長共同子序列長度。若 A[i] 等於 B[j]，這對相符的末字元都能用上，於是 dp[i][j] = 1 + dp[i-1][j-1]——用這個共有的字母延伸較短前綴的最佳對齊。若兩者相異，末字元不可能都在共同子序列裡，所以至少要捨棄一個，得 dp[i][j] = max( dp[i-1][j], dp[i][j-1] )——「忽略 A 的末字元」與「忽略 B 的末字元」中較好的那個。基底情況是 dp[i][0] = 0 與 dp[0][j] = 0，因為任何東西與空字串相比都毫無共享。逐列填這張 (m+1) 乘 (n+1) 的表，花 O(mn) 時間與 O(mn) 空間。

它正確的證明是俐落的剪下貼上：當 A[i] = B[j] 時，可假設任一最佳共同子序列都以這個共有字母結尾（若不然，你可以把它附加上去，得到更長或相等的結果），而把它移除後留下的是較短前綴的最佳最長共同子序列——這就是最佳子結構。要還原真正的子序列而非只有長度，從 dp[m][n] 回溯：在對角配對步驟上，把該字元前置並移到 (i-1, j-1)；否則朝給出最大值的那個鄰居移動。一個有用的對比：共同子序列允許有間隙，而共同子字串必須連續——它們是不同的問題、有不同的動態規劃，把兩者搞混是常見的失誤。