java 最长公共子序列和最长公共子串的动态规划实现

一，基础概念 1 ，什么是子序列？将给定序列中零个或多个元素(如字符)去掉后所得结果。
例如：给定序列【A,B,C,D,E,F,G,H】
子序列：A,C,E,F
同理，【A,H】,【C,D,E】等都是子序列
2 ，什么是子串？给定序列中零个或多个连续的元素(如字符)组成的子序列。
例如：给定序列【A,B,C,D,E,F,G,H】
子序列：C,D,E,F
同理，【C,D,E,F】,【G,H】等都是子串
这里就能明显看出区别，子序列可以不连续，而子串连续。
3 ，什么是最长公共子序列？最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。一个数列，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则称为已知序列的最长公共子序列。
4 ，什么是最长公共子串？最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的，而子串却必须是。
二，求解方案最长公共子序列 1 ，原理动态规划的一个计算两个序列的最长公共子序列的方法如下：
以两个序列 X、Y 为例子：
设有二维数组f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度，则有：
f[1][1] = same(1,1);
f[i,j] = max{f[i-1][j -1] + same(i,j),f[i-1,j],f[i,j-1]};
其中， same(a,b)当 X 的第 a 位与 Y 的第 b 位相同时为“1” ，否则为“0” 。
此时，二维数组中最大的数便是 X 和 Y 的最长公共子序列的长度，依据该数组回溯，便可找出最长公共子序列。
【java 最长公共子序列和最长公共子串的动态规划实现】该算法的空间、时间复杂度均为O(n^2) ，经过优化后，空间复杂度可为O(n) 。