最长公共子序列--动态规划算法

考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bn-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。不难证明有以下性质：

（1） 如果am-1=bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一个最长公共子序列；

（2） 如果am-1!=bn-1，则若zk-1!=am-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列；

（3） 如果am-1!=bn-1，则若zk-1!=bn-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列。

问题的递归式写成：

 

 

回溯输出最长公共子序列过程：

package test;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName: LCS
 * @Description: TODO
 * @author:
 * @Date: 2015-06-29 12:50:14
 */
public class LCS {

    static int MAX=2;
    
    public static List<String> getLCS(int[][] c, int i, int j, String x, String y){
        List<String> t = new ArrayList<String>();
        if(i == 0 || j == 0){
            ;
        }else if(c[i][j] == 1){
            t = getLCS(c,i-1,j-1,x,y);
            if(t.size() == 0)
                t.add("");
            for(int k = 0; k < t.size(); k++){
                String v = t.get(k);
                if(v.length() > 0){
                    int it = Integer.parseInt(v.substring(v.lastIndexOf("(")+1,v.lastIndexOf(",")));
                    if(i - it > 2){
                        t.remove(k);
                        continue;
                    }
                    int jt = Integer.parseInt(v.substring(v.lastIndexOf(",")+1,v.lastIndexOf(")")));
                    if(j - jt > 2){
                        t.remove(k);
                        continue;
                    }
                }
                t.set(k, t.get(k) + x.charAt(i)+"("+i+","+j+")");
            }
        }else if(c[i][j] == 2){
            t = getLCS(c,i-1,j,x,y);
        }else if(c[i][j] == 3){
            t.addAll(getLCS(c,i-1,j,x,y));
            t.addAll(getLCS(c,i,j-1,x,y));
        }else{
            t = getLCS(c,i,j-1,x,y);
        }
        return t;
    }
    
    public static int LCSLength(int[][] c, int i, int j, byte[] xx, byte[] yy,int[][] max){
        
        if(i == 0 || j == 0){
            c[i][j] = 0;
        }else if(xx[i] == yy[j]){
            max[i][j] = 1;    
            c[i][j] = LCSLength(c,i-1,j-1,xx,yy,max)+1;
        }else {
            int ii = LCSLength(c,i-1,j,xx,yy,max);
            int jj = LCSLength(c,i,j-1,xx,yy,max);
            if(ii > jj)
                max[i][j] = 2;
            else if(ii == jj)
                max[i][j] = 3;
                
            c[i][j] = Math.max(ii,jj);
        }
        return c[i][j];
    }
    
    
    public static void main(String[] args){
        String x = " ABCBDAB";
        String y = " BDCABA";
        
        byte[] xx = x.getBytes();
        byte[] yy = y.getBytes();
        
        int c[][] = new int[x.length()][y.length()];
        int max[][] = new int[x.length()][y.length()];
        System.out.println(LCSLength(c,x.length()-1,y.length()-1,xx,yy,max));
        
        List<String> list  = getLCS(max,x.length()-1,y.length()-1,x,y);
        for(String v: list)
            System.out.println(v);
        System.out.print("\n  ");
        for(int j = 1; j < y.length();j++)
            System.out.print(y.charAt(j)+ " ");
        System.out.println("");
        for(int i = 1; i < x.length(); i++){
            System.out.print(x.charAt(i)+ " ");
            for(int j = 1; j < y.length();j++)
                System.out.print(c[i][j]+ " ");
            System.out.println(" ");
        }
        
    }
}