兩個(gè)不同的序列x、y（x的長(zhǎng)度為m，y的長(zhǎng)度為n），求它們的最長(zhǎng)公共子串。（不一定要連續(xù)）
例如：...
這個(gè)問(wèn)題要使用dp求解。

1. 最優(yōu)解
   序列X:
   
   這個(gè)是序列X對(duì)應(yīng)的前i個(gè)的序列
   序列Y
   
   
   序列Z
   

假定序列Z∈LCS(X , Y)。也就是Z是最長(zhǎng)相同子序列
然后從后往前
如果 x_m = y_n,那么z_k = x_m = y_n 這個(gè)是LCS的最后一個(gè)值
如果 x_m != y_n,LCS(k-1) = max( LCS(x_m-1, y_n), LCS(x_m, y_n-1) )

2. 重疊子結(jié)構(gòu)（子問(wèn)題不是獨(dú)立的），因?yàn)樽訂?wèn)題不獨(dú)立，所有會(huì)有很多的重復(fù)計(jì)算。
   如果在壞的情況下（也就是x_m != y_n） ，會(huì)求 情況一 （x的0到m-1、y的n 的LCS） 和情況二（x的0到m、y的n-1 的LCS） 中較長(zhǎng)的序列，這個(gè)計(jì)算有很多重復(fù)操作 ，復(fù)雜度為指數(shù)級(jí)

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