最大公共子序列

典型的动态规划问题

首先找到递推式

image

有了递推式，然后进行初始化

image

数组的最后一个元素的值就为最大公共子序列的长度，具体代码如下

public static void main(String[] args) {
    // TODO Auto-generated method stub
    
    String s1 = "asd";
    String s2 = "sd";
    
    showStr(getLong(s1,s2),s1, s2,s1.length(),s2.length());
    
}


public static int[][] getLong(String s1,String s2) {
    char[] str1 = s1.toCharArray();
    char[] str2 = s2.toCharArray();
    
    int[][] dp = new int[s1.length()+1][s2.length()+1];
    //初始化DP数组
    for(int x=0;x<dp.length;x++) {
        dp[x][0] = 0;
    }
    for(int x=0;x<dp[0].length;x++) {
        dp[0][x] = 0;
    }
    
    for(int x=1;x<dp.length;x++) {
        
        for(int y=1;y<dp[0].length;y++) {
            
            if(str1[x-1]==str2[y-1]) {
                dp[x][y] = dp[x-1][y-1]+1;
            }else {
                dp[x][y] = Math.max(dp[x][y-1], dp[x-1][y]);
            }
            
        }
        
    }
    
    
    
    return dp;
}

public static void showStr(int dp[][],String s1,String s2,int i,int j) {
    if (i == 0 || j == 0) {  
        return;  
    }  
    
    if (s1.charAt(i - 1) == s2.charAt(j - 1)) {  
        showStr(dp, s1, s2, i - 1, j - 1);  
        System.out.print(s1.charAt(i - 1));  
    } else if (dp[i - 1][j] >= dp[i][j]) {  
        showStr(dp, s1, s2, i - 1, j);  
    } else {  
        showStr(dp, s1, s2, i, j - 1);  
    } 
}