序列比對（sequence alignment）
現實世界的比對很少是精確的。拼字檢查器必須看出 "recieve" 與 "receive" 只差一次對調；DNA 工具必須對齊兩個只差幾個突變的基因；diff 必須看出兩個檔案版本大致相同，只有幾行被插入或刪除。序列比對就是這個一般性問題：在允許小差異（插入、刪除、替換）的前提下，度量並找出兩個字串之間最好的對應。
標準的表述把兩個字串排在一起，必要時插入空隙，並用各欄成本的總和為對齊評分：匹配（通常免費）、替換（不匹配懲罰）、或空隙（插入或刪除懲罰）。最佳對齊就是總成本最小（或總分最高）的那一個。這用動態規劃求解。建一個表 D，其中 D[i][j] 是把第一個字串的前 i 個字元與第二個字串的前 j 個字元對齊的最佳成本。遞迴關係是 D[i][j] = 三個選擇的最小值：D[i-1][j-1] 加上「匹配／替換目前這一對」的成本、D[i-1][j] 加上一個空隙（從第一個字串刪除）、以及 D[i][j-1] 加上一個空隙（往第一個字串插入）。依序填表花 O(n*m) 時間與 O(n*m) 空間，而沿著各選擇回溯就能重建出實際的對齊。當匹配成本為 0、不匹配和空隙為 1 時，這恰好是編輯（Levenshtein）距離；配上計分矩陣，它就成為生物資訊學的 Needleman-Wunsch（全域）或 Smith-Waterman（局部）對齊。
序列比對是從精確模式比對通往現實世界所要求的雜亂近似比對的橋樑，也是動態規劃最重要的應用之一。代價是誠實的限制：直接的動態規劃是 O(n*m)，對詞而言沒問題，但對兩整個基因組就很昂貴；這個領域有豐富的加速（只允許少量差異時的帶狀限制、把空間砍到 O(n) 的 Hirschberg 方法、以及像 BLAST 這種以放棄保證最佳換取速度的啟發式工具）。它直接連到最長共同子序列和編輯距離，那兩者是同一張表的特例——其底層的動態規劃機制請見那兩個條目。
以每次替換／空隙成本 1 對齊 "kitten" 和 "sitting"。最佳對齊：把 k 換成 s、把 e 換成 i、並在末尾插入 g——三個操作，所以編輯距離是 3。動態規劃表右下角的格子就裝著這個 3，而沿著選定的最小值箭頭回溯，恰好還原出這三個編輯。
二維動態規劃對每格評分匹配／替換／空隙；角落的格子就是對齊成本。
基本的動態規劃在時間和空間上都是 O(n*m)，對基因組規模的輸入而言太多了——當可以放寬最佳性時，請用帶狀限制、Hirschberg 的線性空間技巧、或 BLAST 這類啟發式方法。編輯距離和最長共同子序列是同一張表的特例，不是另外的演算法。