最長公共子序列LCS-DP

1.最長公共子序列

是指按順序從兩個字元串中擷取的公共包含的元素集合。
ABCDFD
ANNBMMF
ABF就是
           

動态規劃

把一個大問題規劃成好幾個同樣的子問題，然後分别求解。

public class LCSSTRING {

/* 擷取最長 公共子序列 */
public class LCSSTRING {

    /* 獲得狀态轉移數組 即得到一個數組用來存放字元串的資訊實作DP */
    public static int[][] lcs(String x,String y){
        /* 數組前面要包含一個 0行 0 列 然後才接上字元串 的行和列 是以建立的時候要+1*/
        int [][] c = new int[x.length()+][y.length()+];
        /* 循環周遊兩個字元串  */
        for(int i = ;i <=  x.length();i++){
            for(int j = ;j <= y.length();j++){
                System.out.println(" i:" + i + "j :" + j + "str : " + x.charAt(i-) + "  "+ y.charAt(j-));
                /* 字元串相等那麼狀态轉移數組的值 為 左上角 +1 否則取上和左的最大值 */
                 if(x.charAt(i-) == y.charAt(j-)){
                    c[i][j] = c[i-][j-] + ;
                }else if(c[i][j-] >= c[i-][j]){
                    c[i][j] = c[i][j-];
                }else if(c[i][j-] < c[i-][j]){
                    c[i][j] = c[i-][j];
                }

            }
        }
        return c;
    }
    public static void print(int [][]outarr,String x,String y){
        for(int i = ;i < x.length()+;i++){
            for(int j = ; j < y.length()+;j++){
                System.out.print(outarr[i][j] + " ");
            }
            System.out.println();
        }
    }
    /* 輸出字元串 */
    public static void getLcstring(String x,String y,int [][]c){
        /* 此處不能使用兩個for循環，因為兩次for循環是分别進行m*n的周遊，使用一個for循環兩個條件，是要一個不滿足就break。 */
        for(int i = x.length(), j = y.length();i>= && j>=;){

                if(x.charAt(i-) == y.charAt(j-)){
                    System.out.println("element: " + x.charAt(i-)  + "\t" + " i: " + i + " j: "+j);
                    i--;
                    j--;
                }else if(c[i-][j] >= c[i][j-]){
                    i--;
                }else if(c[i-][j] < c[i][j-]){
                    j--;
                }

        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String a = "ABCBDABfsdgsfdr";
        String b = "BDCABAr";
        int [][]result = lcs(a,b);
        print(result,a,b);
        System.out.println(result);
        getLcstring(a,b,result);
        System.out.println("-----end---");
    }

}
           

[[I@1db9742
element: r   i:  j: 
element: A   i:  j: 
element: B   i:  j: 
element: C   i:  j: 
element: B   i:  j: 
-----end---