問題描述：
求兩個字符序列的公共最長子序列。
最長公共子串
在回到子序列問題之前钮糖，先來了解一下子串的問題梅掠。
例如，HISH和FISH兩個字符序列的公共最長子串就是：ISH店归。很容易理解阎抒。
繪制網(wǎng)格
通過上一次背包問題的學(xué)習(xí)，給了我一些很重要的啟示：
- 每種動態(tài)規(guī)劃解決方案都設(shè)計網(wǎng)格消痛。
- 動態(tài)規(guī)劃可以幫助你在給定約束條件下找到最優(yōu)解且叁。
- 問題可分解為彼此獨立且離散的子問題時，就可以使用動態(tài)規(guī)劃法來解決秩伞。
那么逞带，要解決這個問題的網(wǎng)格長什么樣呢？要確定這一點纱新，你首先得回答：
- 1.單元格中的值是什么展氓？
- 2.如何將這個問題劃分成子問題？
- 3.網(wǎng)格的坐標(biāo)軸是什么脸爱？
在動態(tài)規(guī)劃中遇汞，你要將某個指標(biāo)最大化。在這個例子中，你要找出兩個單詞的最長公共子序列空入。hish和fish都包含的最長子序列是什么教寂？hish和vista呢？這就是你要計算的值执庐。
別忘了酪耕，單元格中的值通常就是你要優(yōu)化的值。在這個例子中轨淌，這很可能是一個數(shù)字：兩個字符串都包含的最長子串的長度迂烁。
如何把這個問題劃分成子問題呢？你可能需要比較字符串：不是比較hish和fish递鹉，而是先比較his和fis盟步。每個單元格都將包含著兩個字符串的最長公共字符串的長度□锝幔或許有了一些線索：
填充網(wǎng)格
現(xiàn)在却盘，你很清楚網(wǎng)格應(yīng)是怎么樣的。填充該網(wǎng)格的每個單元格時媳拴，該使用什么樣的公式呢黄橘？由于你已經(jīng)知道了答案——hish和fish的最長子序列為ish，所以可以作點弊屈溉。
幾遍如此塞关，你還是不能確定該使用什么樣的公式。計算機科學(xué)家有時會開玩笑說子巾，那就使用費曼算法（Feynman algorithm）帆赢。這個算法是以注明物理學(xué)家理查德·費曼命名的，其步驟如下：
實際上线梗，根本沒有找出計算公式的簡單辦法椰于，你必須通過嘗試才能找出管用的公式。有些算法并非精確的解決步驟仪搔，而只是幫助你理清思路的框架瘾婿。
最終的網(wǎng)格
可以從其中總結(jié)出以下的規(guī)律：
實現(xiàn)這個公式的偽代碼大概長這樣：
if (chars1[i - 1] == chars2[j - 1]) {
array[i][j] = array[i - 1][j - 1] + 1;
} else {
array[i][j] = 0
}
需要注意的一點是，這個問題的最終答案并不一定在最后一個單元格中僻造！對于前面的背包問題憋他，最終答案總是在最后的單元格中。單對于LCS問題來說髓削，答案為網(wǎng)格中最大的數(shù)字——它可能并不位于最后的單元格中竹挡。例如單詞hish和vista的最長公共子串時，網(wǎng)格如下：
最長公共子序列
假設(shè)Alex不小心輸入了fosh立膛，那么它原本是想輸入fish還是fort呢揪罕？我們使用最長子序列來比較它們梯码。
最長公共個子串的長度相同，都包含兩個字母好啰。但fosh與fish更像轩娶。
這里比較的是最長公共子串，但其實應(yīng)該比較最長子序列：兩個單詞中都有的序列包含的字數(shù)框往。如何計算最長公共子序列呢鳄抒？
下面是用于計算fish和fosh的最長公共子序列的網(wǎng)格：
下面是填寫這個網(wǎng)格的公式：
偽代碼大概長這樣：
if (chars1[i - 1] == chars2[j - 1]) {
array[i][j] = array[i - 1][j - 1] + 1;
} else {
array[i][j] = max{array[i -1][j] , array[i][j - 1] };
}
代碼實現(xiàn)：
整個程序是從自己的算法學(xué)習(xí)程序中直接扒下來的，inputList保存的是從文本文件中一行一行讀取到的數(shù)值椰弊，outputList保存的是要輸出到文本文件中的數(shù)據(jù)许溅。由于要輸出，所以定義了一個boolean類型的isRowBig標(biāo)志位秉版，用來判斷哪一個字符串的長度更長贤重，然后獲取更長的那個輸出。雖然實現(xiàn)了代碼清焕，但是感覺自己寫得很丑陋并蝗。
/**
* 獲取數(shù)據(jù)之后返回數(shù)據(jù)到輸出Array中
*/
private void getResult() {
// 獲取數(shù)值
int rowSize = inputList.get(0).length();
int colSize = inputList.get(1).length();
int[][] array = new int[rowSize + 1][colSize + 1];
char[] chars1 = inputList.get(0).toCharArray();
char[] chars2 = inputList.get(1).toCharArray();
String temp = new String();
// 初始化數(shù)組
for (int i = 0; i < rowSize; i++) array[i][0] = 0;
for (int i = 0; i < colSize; i++) array[0][i] = 0;
// 填空
boolean isRowBig = true;
if (rowSize >= colSize) {
isRowBig = true;
} else {
isRowBig = false;
} // 雖然實現(xiàn)了代碼，但是感覺寫得特別丑陋秸妥。
for (int i = 1; i <= rowSize; i++) {
for (int j = 1; j <= colSize; j++) {
if (chars1[i - 1] == chars2[j - 1]) {
array[i][j] = array[i - 1][j - 1] + 1;
if (isRowBig) {
temp += chars2[j - 1];
} else {
temp += chars1[i - 1];
} // end if:正確向temp中添加了字符
} else if (array[i - 1][j] >= array[i][j - 1]) {
array[i][j] = array[i - 1][j];
} else {
array[i][j] = array[i][j - 1];
}
}
} // end for:array和temp中已經(jīng)保存了正確的數(shù)據(jù)
outputList.add(temp);
}
歡迎轉(zhuǎn)載滚停，轉(zhuǎn)載請注明出處！
簡書ID：@我沒有三顆心臟
github：wmyskxz
歡迎關(guān)注公眾微信號：wmyskxz_javaweb
分享自己的Java Web學(xué)習(xí)之路以及各種Java學(xué)習(xí)資料
