两个不同的序列x、y（x的长度为m，y的长度为n），求它们的最长公共子串。（不一定要连续）
例如：...
这个问题要使用dp求解。
- 最优解
序列X:这个是序列X对应的前i个的序列
序列Y
序列Z
假定序列Z∈LCS(X , Y)。也就是Z是最长相同子序列
然后从后往前
如果 x_m = y_n,那么z_k = x_m = y_n 这个是LCS的最后一个值
如果 x_m != y_n,LCS(k-1) = max( LCS(x_m-1, y_n), LCS(x_m, y_n-1) )
- 重叠子结构（子问题不是独立的），因为子问题不独立，所有会有很多的重复计算。
如果在坏的情况下（也就是x_m != y_n） ，会求 情况一 （x的0到m-1、y的n 的LCS） 和情况二（x的0到m、y的n-1 的LCS） 中较长的序列，这个计算有很多重复操作 ，复杂度为指数级
Integer[][] c;
int count = 0;
public LCS(int x, int y){
c = new Integer[x+1][y+1];
}
public int getLcs(char[] x, char[] y, int i, int j){
if(i < 0 || j < 0){
return 0;
}
if(c[i][j] == null){
if(x[i] == y[j]){
c[i][j] = getLcs(x, y, i-1, j-1) + 1;
}else{
c[i][j] = Math.max(getLcs(x, y, i - 1, j), getLcs(x, y, i, j - 1));
}
}
if(i == 5 && j == 5){
System.out.println("------------------------");
for (int m = 0; m < x.length; m++) {
for (int n = 0; n < y.length; n++) {
Integer x1 = (c[m][n]==null) ? 7 : c[m][n];
System.out.print(x1 + " ");
}
System.out.println();
}
}
return c[i][j];
}
0 1 7 7 7 7
0 1 2 7 7 7
0 1 7 3 7 7
0 1 2 3 4 7
0 1 2 3 4 5
7 1 2 3 4 5
