LCS问题

1: 主要讲回溯法要旨：

dp[i-1][j-1]       dp[i-1[j]
dp[i][j-1]          dp[i][j]

如果 dp[i][j] == dp[i][j-1] +1 并且
dp[i][j] == dp[i-1][j] +1 并且
dp[i][j] == dp[i-1][j-1] +1
则斜向45度向左搜索下一个字符
否则朝 max(dp[i-1][j],dp[i][j-1]) 方向搜索

public class Main8 {

public static void main(String[] args) {

    char[] chara = "abdccxz".toCharArray();
    char[] charb = "adcdcy".toCharArray();

    int dp[][] = new int[chara.length + 1][charb.length + 1];

    for (int i = 0; i < chara.length; i++) {
        for (int j = 0; j < charb.length; j++) {
            if (chara[i] == charb[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
            } else {
                dp[i + 1][j + 1] = Integer.max(dp[i][j + 1], dp[i + 1][j]);
            }
        }
    }

    print(dp, charb, chara);

    int length = dp[chara.length][charb.length];

    StringBuilder sb = new StringBuilder(length);

    int j = charb.length;
    int i = chara.length;


    while (true) {
        if (dp[i][j] == dp[i][j - 1] + 1 && dp[i][j] == dp[i - 1][j] + 1 && dp[i][j] == dp[i - 1][j - 1] + 1) {
            j--;
            i--;
            sb.append(charb[j]);
            length--;
        } else {
            if (dp[i - 1][j] >= dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        if (length == 0) {
            break;
        }
    }


    System.out.println(sb.reverse().toString());
}

public static void print(int dp[][], char[] a, char[] b) {

    System.out.print(0 + "\t");
    for (char ac : a) {
        System.out.print(ac + "\t");
    }
    System.out.println();

    for (int i = 1; i < dp.length; i++) {
        System.out.print(b[i - 1] + "\t");
        for (int j = 1; j < dp[0].length; j++) {
            System.out.print(dp[i][j] + "\t");
        }
        System.out.println();
    }
    System.out.println();
}

}