2018-07-02 14:39:18
最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。一个数列 ，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则称为已知序列的最长公共子序列。
最长公共子序列问题是一个经典的计算机科学问题，也是数据比较程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。
最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置。而最长公共子串（要求连续）和最长公共子序列是不同的。
一、最长公共子序列
对于LCS问题来说，有如下的递推式：
c[i,j]表示：(x1,x2....xi) 和 (y1,y2...yj) 的最长公共子序列的长度。
二、最长公共子串
递推式为：dp[i][j] = dp[i - 1][j - 1] + 1 if (xi == yj)
dp[i][j] = 0 else
问题描述：
问题求解：
public int findLength(int[] A, int[] B) {
int res = 0;
int[][] dp = new int[A.length][B.length];
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < B.length; j++) {
if (A[i] == B[j]) {
if (i == 0 || j == 0) dp[i][j] = 1;
else {
dp[i][j] = dp[i - 1][j - 1] + 1;
res = Math.max(res, dp[i][j]);
}
}
else dp[i][j] = 0;
}
}
return res;
}