LCS

两个不同的序列x、y（x的长度为m，y的长度为n），求它们的最长公共子串。（不一定要连续）
例如：...
这个问题要使用dp求解。

1. 最优解
   序列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) )

2. 重叠子结构（子问题不是独立的），因为子问题不独立，所有会有很多的重复计算。
   如果在坏的情况下（也就是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