最長(zhǎng)公共子序列是一個(gè)很經(jīng)典的動(dòng)態(tài)規(guī)劃問題，最近正在學(xué)習(xí)動(dòng)態(tài)規(guī)劃，所以拿來(lái)這里再整理一下。
這個(gè)問題在《算法導(dǎo)論》中作為講動(dòng)態(tài)規(guī)劃算法的例題出現(xiàn)。
動(dòng)態(tài)規(guī)劃，眾所周知，第一步就是找子問題，也就是把一個(gè)大的問題分解成子問題。這里我們?cè)O(shè)兩個(gè)字符串A、B，A = "a0, a1, a2, ..., am-1"，B = "b0, b1, b2, ..., bn-1"。
（1）如果am-1 == bn-1，則當(dāng)前最長(zhǎng)公共子序列為"a0, a1, ..., am-2"與"b0, b1, ..., bn-2"的最長(zhǎng)公共子序列與am-1的和。長(zhǎng)度為"a0, a1, ..., am-2"與"b0, b1, ..., bn-2"的最長(zhǎng)公共子序列的長(zhǎng)度+1。
（2）如果am-1 != bn-1，則最長(zhǎng)公共子序列為max（"a0, a1, ..., am-2"與"b0, b1, ..., bn-1"的公共子序列，"a0, a1, ..., am-1"與"b0, b1, ..., bn-2"的公共子序列）
如果上述描述用數(shù)學(xué)公式表示，則引入一個(gè)二維數(shù)組c[][]，其中c[i][j]記錄X[i]與Y[j]的LCS長(zhǎng)度，b[i][j]記錄c[i][j]是通過(guò)哪一個(gè)子問題的值求得的，即，搜索方向。
這樣我們可以總結(jié)出該問題的遞歸形式表達(dá)：
按照動(dòng)態(tài)規(guī)劃的思想，對(duì)問題的求解，其實(shí)就是對(duì)子問題自底向上的計(jì)算過(guò)程。這里，計(jì)算c[i][j]時(shí)，c[i-1][j-1]、c[i-1][j]、c[i][j-1]已經(jīng)計(jì)算出來(lái)了，這樣，我們可以根據(jù)X[i]與Y[j]的取值，按照上面的遞推，求出c[i][j]，同時(shí)把路徑記錄在b[i][j]中（路徑只有3中方向：左上、左、上，如下圖）。
計(jì)算c[][]矩陣的時(shí)間復(fù)雜度是O(m*n)；根據(jù)b[][]矩陣尋找最長(zhǎng)公共子序列的過(guò)程，由于每次調(diào)用至少向上或向左移動(dòng)一步，這樣最多需要（m+n）次就會(huì)i = 0或j = 0，也就是算法時(shí)間復(fù)雜度為O(m+n)。
