动态规划实例（二）：最长公共子序列（LCS）_实验七动态规划第二关 最长公共子序列

    给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。比如字符串1：BDCABA；字符串2：ABCBDAB，则这两个字符串的最长公共子序列长度为4，最长公共子序列是：BCBA

    设 X=(x1,x2,.....xn) 和 Y={y1,y2,.....ym} 是两个序列，将 X 和 Y 的最长公共子序列记为LCS(X,Y)，找出LCS(X,Y)就是一个最优化问题。因为，我们需要找到X 和 Y中最长的那个公共子序列。而要找X 和 Y的LCS，首先考虑X的最后一个元素和Y的最后一个元素。

    重叠子问题是啥？就是说原问题 转化 成子问题后，  子问题中有相同的问题。咦？我怎么没有发现上面的三个子问题中有相同的啊？？？？

    关键是采用动态规划时，并不需要去一 一 计算那些重叠了的子问题。或者说：用了动态规划之后，有些子问题 是通过 “查表“ 直接得到的，而不是重新又计算一遍得到的。废话少说：举个例子吧！比如求Fib数列。

    LCS具体实例及实现代码如下所示：

/**
 * @Title: LCS.java
 * @Package dynamicprogramming
 * @Description: TODO
 * @author peidong
 * @date 2017-6-5 上午9:34:15
 * @version V1.0
 */
package dynamicprogramming;

import java.util.Stack;

/**
 * @ClassName: LCS
 * @Description: 最长公共子序列
 * @date 2017-6-5 上午9:34:15
 *
 */

public class LCS {
    /**
     *
     * @Title: lcs1
     * @Description: 递归的方式获取最长公共子序列
     * @param x  字符串数组
     * @param y  字符串数组
     * @param m  数组长度
     * @param n  数组长度
     * @return
     * @return int
     * @throws
     */
    public static int lcs1(char[] x, char[] y, int m, int n){
        //边界条件判断
        if(m == 0 || n ==0)
            return 0;
        if(x[m-1] == y[n-1])
            return 1 + lcs1(x, y, m-1, n-1);
        else
            return max(lcs1(x, y, m-1, n), lcs1(x, y, m, n-1));
    }

    /**
     *
     * @Title: max
     * @Description: 返回较大值
     * @param a
     * @param b
     * @return
     * @return int
     * @throws
     */
    public static int max(int a, int b){
        return (a > b) ? a : b;
    }

    /**
     *
     * @Title: lcs2
     * @Description: 动态规划求解最长公共子串
     * @param x   字符串数组
     * @param y   字符串数组
     * @param m   数组长度
     * @param n   数组长度
     * @return int
     * @throws
     */
    public static int lcs2(char[] x, char[] y, int m, int n){
        //初始化数组
        int[][] L = new int[m+1][n+1];

        //求解过程
        for(int i = 0; i <= m; i++){
            for(int j = 0; j <= n; j++){
                if( i == 0 || j == 0){
                    L[i][j] = 0;
                }else if( x[i - 1] == y[j - 1]){
                    L[i][j] = L[i - 1][j - 1] + 1;
                }else{
                    L[i][j] = max(L[i][j - 1], L[i - 1][j]);
                }
            }
        }
        Stack<Character> stack = new Stack();
        int m1 = x.length - 1;
        int n1 = y.length - 1;
        while (n1 >= 0 && m1 >= 0) { // 遍历数组
            if (x[m1] == y[n1]) {
                stack.push(x[m1]);
                m1--;
                n1--;
            } else {// 字符不同时，根据打印出的二维矩阵（测试数据）查找上一个相同的字符
                if (L[m1 + 1][n1] > L[m1][n1 + 1]) {
                    n1--;
                } else {
                    m1--;
                }
            }
        }
        System.out.println("最长公共子序列为：");
        while (!stack.isEmpty()) {// 打印出最长的递增子序列
            System.out.print(stack.pop() + ",");
        }
        return L[m][n];
    }

    /**
     * @Title: main
     * @Description: TODO
     * @param args
     * @return void
     * @throws
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        char[] x ={'A', 'G', 'G', 'T', 'A', 'B'};
        char[] y = {'G', 'X', 'T', 'X', 'A', 'Y', 'B'};
        int m = x.length;
        int n = y.length;

        int res1 = lcs1(x, y, m, n);
        int res2 = lcs2(x, y, m, n);
        System.out.println();
        System.out.println("使用递归获取最长公共子序列长度为：" + res1);
        System.out.println("使用dp获取最长公共子序列长度为：" + res2);
    }

}