算法学习——动态规划例题：最长公共子序列问题（java）详解过程

灰太狼 2021-09-28 08:50 130阅读 0赞

package DTGH;
    
    /*
        最长公共子序列
            一个给定序列的子序列是在该序列中删去若千元素后得到的序列
            给定两个序列X和Y ,当另一-序列Z既是X的子序列又是Y的子序列时,称Z是序
            列X和Y的公共子序列
        最长公共子序列,
    .       X=(A,B,C,B,D,A,B) Y= (B,D,C,A,B, A)●(B,C,B,A) (B,D, A, B)
     */
    public class LongSonString {
        // 暴力法解决
        public int search(int xi, int yi, char[] X, char[] Y) {
            //dp返回条件
            if (xi == x.length  || yi == y.length) {
                return 0;
            }
            //判断当前xi和yi是否相等
            if (x[xi] == y[yi]) {
                return bl(xi + 1, yi + 1, x, y) + 1;
            }
            return Math.max(bl(xi + 1, yi, x, y), bl(xi, yi + 1, x, y));
        }
    
        //记忆化搜索动态的雏形
       //记忆化搜索 res 初始化为-1
        public static int jyh(int xi, int yi, char[] x, char[] y,int[][] res) {
            //dp返回条件
            if (xi == x.length - 1 || yi == y.length) {
                return 0;
            }
            if(res[xi][yi]!=-1){
                return res[xi][yi];
            }
            //判断当前xi和yi是否相等
            if (x[xi] == y[yi]) {
                 res[xi][yi]=bl(xi + 1, yi + 1, x, y) + 1;
                return res[xi][yi];
            }else {
                res[xi][yi] = Math.max(bl(xi + 1, yi, x, y), bl(xi, yi + 1, x, y));
                return res[xi][yi];
            }
        }
        //动态规划
        public static int dtgh(char[] x,char[] y){
            int res[][] =new int[x.length+1][y.length+1];
            for (int i = 1; i <=x.length ; i++) {
                for (int j = 1; j <=y.length ; j++) {
                    if (x[i-1]==y[j-1]){
                        res[i][j]=res[i-1][j-1]+1;
                    }else{
                        res[i][j]=Math.max(res[i-1][j],res[i][j-1]);
                    }
                }
            }
            return res[x.length][y.length];
        }
    
        public static void main(String[] args) {
            LongSonString a = new LongSonString();
            char[] x = {'A', 'B', 'C', 'B', 'D', 'A', 'B'};
            //char[] y = {'A', 'B', 'B','B', 'D', 'A', 'B'};
            char[] y = {'B', 'D', 'C', 'A', 'B', 'A'};
            int[][] res = new int[x.length][y.length];
            for (int i = 0; i < x.length; i++) {
                for (int j = 0; j < y.length; j++) {
                    res[i][j] = -1;
                }
            }
    
             System.out.println(DTGH_LongPublicString.bl(0, 0, x, y));
            System.out.println(DTGH_LongPublicString.dtgh(x, y));
        }
    }