题目
给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符串2:ABCBDAB
则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
/*
* 以下dp[0...M-1]相当于dp[0]~dp[M-1]
* str1.length = M;str2.length = N ==>生成M*N大小的dp矩阵,
* dp[i][j]的含义:str1[0...i]和str2[0...j]的最长公共子序列的长度
* 从左到右,从上到下,计算dp矩阵
* 1.dp第一列即dp[0...M-1][0],dp[i][0]的含义是str1[0..i]和str2[0]的最长公共子序列的长度
* str2[0]只有一个字符,所以dp[i][0]最大为1,
* 如果str1[i]==str2[0] ==> dp[i][0]=1 ==> dp[i+1...M-1][0]=1;
* 2.dp第一行同第一列,如果str2[j] == str1[0] ==> dp[0][j]=1 ==> dp[0][j+1...N-1]=1;
* 3.其他位置的dp[i][j]有如下三种情况:
* a.可能是dp[i-1][j],代表str1[0...i-1]与str2[0...j]的最长公共子序列长度
* b.可能是dp[i][j-1],代表str1[0...i]与str2[0...j-1]的最长公共子序列的长度
* c.可能是dp[i-1][j-1]+1,当str1[i]==str2[j]时
* 4.dp矩阵右下角的值代表str1和str2整体的最长公共子序列长度,从右下角开始,有三种移动方式,向上、向左、向左上;i表示当前行数,j表示当前列数
* 5.如果dp[i][j] > dp[i-1][j]和dp[i][j-1],说明在计算dp[i][j]的时候选择了决策dp[i-1][j-1]+1,确定str1[i]=str2[j],
* 将该字符放入res,向左上方移动;
* 6.如果dp[i][j] == dp[i-1][j]说明之前dp[i-1][j-1]+1这个决策不是必须的选择,向上方移动即可;
* 7.如果dp[i][j] == dp[i][j-1]说明之前dp[i-1][j-1]+1这个决策不是必须的选择,向左方移动即可;
*/
public class 最长公共子序列问题 { public static int[][] getdp(char[] str1,char[] str2){ int[][] dp = new int[str1.length][str2.length]; dp[0][0] = str1[0] == str2[0] ? 1 : 0; for(int i = 1;i < str1.length;i++) { dp[i][0] = Math.max(dp[i-1][0], str1[i] == str2[0] ? 1 : 0); } for(int j = 1;j < str2.length;j++) { dp[0][j] = Math.max(dp[0][j-1], str1[0] == str2[j] ? 1 : 0); } for(int i = 1;i= 0) { if(n > 0 && dp[m][n] == dp[m][n-1]) { n--; }else if(m > 0 && dp[m][n] == dp[m-1][n]) { m--; }else { res[index--] = chs1[m]; m--; n--; } } return String.valueOf(res); } public static void main(String[] args) { String str1 = "A1BC2D3EFGH45I6JK7LMN"; String str2 = "12OPQ3RST4U5V6W7XYZ"; System.out.println(lcse(str1, str2)); } }