兩個不同的序列x唧垦、y（x的長度為m撒桨，y的長度為n），求它們的最長公共子串墨坚。（不一定要連續(xù)）
例如：...
這個問題要使用dp求解秧饮。
- 最優(yōu)解
序列X:這個是序列X對應(yīng)的前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) )
- 重疊子結(jié)構(gòu)（子問題不是獨立的）泽篮，因為子問題不獨立盗尸，所有會有很多的重復(fù)計算。
如果在壞的情況下（也就是x_m != y_n） 咪辱，會求 情況一 （x的0到m-1振劳、y的n 的LCS） 和情況二（x的0到m、y的n-1 的LCS） 中較長的序列油狂，這個計算有很多重復(fù)操作 历恐，復(fù)雜度為指數(shù)級
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
