最長的共同子序列
動態規劃最重要的實現之一是找出最長公共子序列 。我們先來定義一些基本術語。
子序列：
子序列是可以通過刪除一些元素而不改變其餘元素的順序從另一序列匯出的序列。假設我們有一個字串 ABC 。如果我們從這個字串中刪除零個或一個或多個字元，我們得到該字串的子序列。所以字串 ABC 的子序列將是{ A ， B ， C ， AB ， AC ， BC ， ABC ， “” }。即使我們刪除所有字元，空字串也將是一個子序列。為了找出子序列，對於字串中的每個字元，我們有兩個選項 - 要麼我們接受字元，要麼我們不接受。因此，如果字串的長度為 n ，則該字串有 2 個 n 個子序列。
最長的共同子序列：
顧名思義，在兩個字串之間的所有公共子序列中，最長的公共子序列（LCS）是具有最大長度的子序列。例如： HELLOM 和 HMLD 之間的共同子序列是 H ， HL ， HM 等。這裡 HLL 是長度為 3 的最長公共子序列。
蠻力方法：
我們可以使用回溯生成兩個字串的所有子序列。然後我們可以比較它們以找出常見的子序列。在我們需要找出具有最大長度的那個之後。我們已經看到，長度為 n 的字串有 2 個 n 個子序列。如果我們的 n 超過 **20-25，**那麼解決問題需要數年時間。
動態程式設計方法：
讓我們用一個例子來接近我們的方法。假設我們有兩個字串 abcdaf 和 acbcf 。讓我們用 s1 和 s2 表示這些。因此，這兩個字串的最長公共子序列將是 abcf ，其長度為 4.再次提醒你，子序列不需要在字串中連續。為了構建 ABCF ，我們忽略了 阿凡達 中的 S1 和 C 的 S2 。我們如何使用動態程式設計找到它？
我們將從一個表（一個二維陣列）開始，該表包含連續 s1 的所有字元以及列中 s2 的所有字元。這裡的表是 0 索引的，我們將字元從 1 開始向前。我們將每行從左到右遍歷表格。我們的表格如下：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
這裡每行和每列表示兩個字串之間最長公共子序列的長度，如果我們取出該行和列的字元並新增到它之前的字首。例如： 表[2] [3] 表示 ac 和 abc 之間最長公共子序列的長度。
第 0 列表示 s1 的空子序列。類似地，第 0 行表示 s2 的空子序列。如果我們取一個字串的空子序列並嘗試將其與另一個字串匹配，則無論第二個子字串的長度是多長，公共子序列的長度都為 0。所以我們可以用 0 來填充第 0 行和第 0 列。我們得到：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
讓我們開始。當我們填寫表[1] [1]時，我們問自己，如果我們有一個字串 a 和另一個字串 a 而沒有別的，這裡最常見的子序列是什麼？這裡 LCS 的長度為 1.現在讓我們看一下表[1] [2] 。我們有字串 ab 和字串 a 。LCS 的長度為 1.如你所見，其餘值對於第一行也是 1，因為它只考慮字串 a 與 abcd ， abcda ， abcdaf 。所以我們的表格看起來像：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
對於第 2 行，現在將包括 c 。對於表[2] [1]，我們在一側有一個 ac，在另一側有一個。所以 LCS 的長度是 1.我們從哪裡得到這個 1？從頂部，其表示該 LCS 一個 2 子之間。所以我們所說的是，如果 s1 [2] 和 s2 [1] 不相同，那麼 LCS 的長度將是頂部或左側 LCS 長度的最大值。將 LCS 的長度置於頂部表示，我們不從 s2 獲取當前字元。類似地，在左側取 LCS 的長度表示，我們不從當前字元中取出 s1 建立 LCS。我們得到：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
所以我們的第一個公式是：
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
繼續，對於表[2] [2]，我們有字串 ab 和 ac 。由於 c 和 b 不相同，我們在這裡放置頂部或左側的最大值。在這種情況下，它又是 1.在那之後，對於表[2] [3]，我們有字串 abc 和 ac 。此時行和列的當前值都相同。現在 LCS 的長度將等於 LCS 的最大長度+ 1。到目前為止，我們如何獲得 LCS 的最大長度？我們檢查對角線值，它代表 ab 和 a 之間的最佳匹配。從這個狀態，對於當前值，我們又向 s1 和 s 新增了一個字元 s2 碰巧是一樣的。所以 LCS 的長度當然會增加。我們把 1 + 1 = 2 在表[2] [3] 。我們得到了，
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
所以我們的第二個公式是：
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
我們已經定義了這兩種情況。使用這兩個公式，我們可以填充整個表。填滿表後，它將如下所示：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
+-----+-----+-----+-----+-----+-----+-----+-----+
s1 和 s2 之間的 LCS 長度將為表[5] [6] = 4 。這裡，5 和 6 分別是 s2 和 s1 的長度。我們的虛擬碼將是：
Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
Table[0][i] = 0
endfor
for i from 1 to s2.length
Table[i][0] = 0
endfor
for i from 1 to s2.length
for j from 1 to s1.length
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
else
Table[i][j] = max(Table[i-1][j], Table[i][j-1])
endif
endfor
endfor
Return Table[s2.length][s1.length]
該演算法的時間複雜度為： O(mn) 其中 m 和 n 表示每個字串的長度。
我們如何找出最長的共同子序列？我們將從右下角開始。我們將檢查價值的來源。如果該值來自對角線，即如果 Table [i-1] [j-1] 等於 Table [i] [j] -1 ，則我們推 s2 [i] 或 s1 [j] （兩者都是是相同的）並對角移動。如果該值來自 top，這意味著，如果 Table [i-1] [j] 等於 Table [i] [j] ，我們將移至頂部。如果值來自左邊，那意味著，如果 Table [i] [j-1] 等於 Table [i] [j] ，我們向左移動。當我們到達最左側或最頂部的列時，我們的搜尋結束。然後我們從堆疊中彈出值並列印它們。虛擬碼：
Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
S.push(s1[j]) //or S.push(s2[i])
i := i - 1
j := j - 1
else if Table[i-1][j] == Table[i][j]
i := i-1
else
j := j-1
endif
endwhile
while S is not empty
print(S.pop)
endwhile
需要注意的是：如果表[i-1] [j] 和表[i] [j-1] 都等於表[i] [j] 並且表[i-1] [j-1] 不是等於表[i] [j] - 1 ，那個時刻可以有兩個 LCS。這個虛擬碼不考慮這種情況。你必須遞迴地解決這個問題才能找到多個 LCS。
該演算法的時間複雜度為： O（max(m, n)） 。