最长公共子序列

 问题：

　　求解两个数组的最长公共子序列LCS（Longest Common Subsequence）。

思路：

　　如果要求一个问题的最优解（通常是最大值或者最小值），而且该问题能够分解成若干个子问题，并且小问题之间也存在重叠的子问题，则考虑采用动态规划。

　　设 X=(x1,x2,.....xn) 和 Y={y1,y2,.....ym} 是两个序列，将 X 和 Y 的最长公共子序列记为LCS(X,Y)。

　　1. 如果 x[n] = y[m]，则LCS(X,Y) = LCS( X[n-1], Y[m-1] )。
　　2. 如果 x[n] != y[m]，则LCS(X,Y) = MAX{ LCS( X[n-1], Y[m] ), LCS( X[n], Y[m-1] )}。

示例：

X= "BDCABA";

Y= "ABCBDAB";

code:

public class LCSequence {
    public static int LCS(String X, String Y){
        int[][] c = new int[X.length()+1][Y.length()+1];
        for (int i = 0; i <= X.length(); i++) {//x为空时初始化
            c[i][0] = 0;
        }
        for (int i = 0; i <= Y.length(); i++) {
            c[0][i] = 0;
        }

        for (int i = 1; i <= X.length(); i++) {
            for (int j = 1; j <= Y.length(); j++) {

                if (X.charAt(i-1) == Y.charAt(j-1))
                    c[i][j] = c[i-1][j-1] + 1;
                else if ( c[i-1][j] > c[i][j-1])
                    c[i][j] = c[i-1][j];
                else
                    c[i][j] = c[i][j-1];
            }
        }
        return c[X.length()][Y.length()];

    }

    public static void main(String[] args) {
        String str1 = "BDCABA";
        String str2 = "ABCBDAB";
        int result = LCS(str1, str2);
        System.out.println(result);
    }
}