最长公共子序列问题
问题描述：
求两个字符序列的公共最长子序列。
最长公共子串
在回到子序列问题之前，先来了解一下子串的问题。 例如，HISH和FISH两个字符序列的公共最长子串就是：ISH。很容易理解。
绘制网格
通过上一次背包问题的学习，给了我一些很重要的启示：
- 每种动态规划解决方案都设计网格。
- 动态规划可以帮助你在给定约束条件下找到最优解。
- 问题可分解为彼此独立且离散的子问题时，就可以使用动态规划法来解决。
那么，要解决这个问题的网格长什么样呢？要确定这一点，你首先得回答：
- 1.单元格中的值是什么？
- 2.如何将这个问题划分成子问题？
- 3.网格的坐标轴是什么？
在动态规划中，你要将某个指标最大化。在这个例子中，你要找出两个单词的最长公共子序列。hish和fish都包含的最长子序列是什么？hish和vista呢？这就是你要计算的值。
别忘了，单元格中的值通常就是你要优化的值。在这个例子中，这很可能是一个数字：两个字符串都包含的最长子串的长度。
如何把这个问题划分成子问题呢？你可能需要比较字符串：不是比较hish和fish，而是先比较his和fis。每个单元格都将包含着两个字符串的最长公共字符串的长度。或许有了一些线索：
填充网格
现在，你很清楚网格应是怎么样的。填充该网格的每个单元格时，该使用什么样的公式呢？由于你已经知道了答案——hish和fish的最长子序列为ish，所以可以作点弊。
几遍如此，你还是不能确定该使用什么样的公式。计算机科学家有时会开玩笑说，那就使用费曼算法（Feynman algorithm）。这个算法是以注明物理学家理查德·费曼命名的，其步骤如下：
实际上，根本没有找出计算公式的简单办法，你必须通过尝试才能找出管用的公式。有些算法并非精确的解决步骤，而只是帮助你理清思路的框架。
最终的网格
可以从其中总结出以下的规律：
实现这个公式的伪代码大概长这样：
if (chars1[i - 1] == chars2[j - 1]) {
array[i][j] = array[i - 1][j - 1] + 1;
} else {
array[i][j] = 0
}需要注意的一点是，这个问题的最终答案并不一定在最后一个单元格中！对于前面的背包问题，最终答案总是在最后的单元格中。单对于LCS问题来说，答案为网格中最大的数字——它可能并不位于最后的单元格中。例如单词hish和vista的最长公共子串时，网格如下：
最长公共子序列
假设Alex不小心输入了fosh，那么它原本是想输入fish还是fort呢？我们使用最长子序列来比较它们。
最长公共个子串的长度相同，都包含两个字母。但fosh与fish更像。
这里比较的是最长公共子串，但其实应该比较最长子序列：两个单词中都有的序列包含的字数。如何计算最长公共子序列呢？
下面是用于计算fish和fosh的最长公共子序列的网格：
下面是填写这个网格的公式：
伪代码大概长这样：
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] };
}代码实现：
整个程序是从自己的算法学习程序中直接扒下来的，inputList保存的是从文本文件中一行一行读取到的数值，outputList保存的是要输出到文本文件中的数据。由于要输出，所以定义了一个boolean类型的isRowBig标志位，用来判断哪一个字符串的长度更长，然后获取更长的那个输出。虽然实现了代码，但是感觉自己写得很丑陋。
/**
* 获取数据之后返回数据到输出Array中
*/
private void getResult() {
// 获取数值
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();
// 初始化数组
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;
} // 虽然实现了代码，但是感觉写得特别丑陋。
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中已经保存了正确的数据
outputList.add(temp);
}腾讯云开发者
