算法练习(25) - 动态规划:最长子序列

问题

求解两个数组的最长子序列
例如 :

int[] x = {1,2,3,4,4,5}
int[] y = {1,4,5}

最长子串为 : 1,4,5

code

public class _05LCSTest {

    @Test
    public void LCS_test() {
        String[] s1 = {"1","3","4","5"};
        String[] s2 = {"0","1","3","5"};
        printLCS(s1,s2);
    }

    public void printLCS(String[] str1, String[] str2) {

        int[][] clen = new int[str1.length +1][str2.length+1];

        for (int i = 1; i <= str1.length; i++) {
            for (int j = 1; j <= str2.length; j++) {
                 if(str1[i-1].equals(str2[j-1])){
                     clen[i][j] = clen[i-1][j-1] + 1;
                }else {
                    clen[i][j] =  Math.max(clen[i][j-1],clen[i-1][j]);
                }
            }
        }
        int i = str1.length;
        int j = str2.length;
        StringBuilder sb = new StringBuilder();
        while(i>0 && j > 0){
            if(str1[i-1].equals(str2[j-1])){
                sb.append(str1[i-1]);
                i--;
                j--;
            }else{
                if(clen[i-1][j] > clen[i][j-1] ){
                    i--;
                }else if(clen[i-1][j] < clen[i][j-1] ){
                    j--;
                }else  if(clen[i-1][j] == clen[i][j-1] ){
                    j--;
                }
            }
        }
        System.out.println(sb.reverse().toString());
    }
}

解析