最长公共子序列问题

给定两个字符串str1和str2，返回两个字符串的最长公共子序列。
str1=“1A2C3D4B56”，str2=“B1D23CA45B6A”。
“123456”或者“12C4B6”都是最长公共子序列，返回哪一个都行。

思路

dp[i][j]的含义是str1[0..i]与str2[0..j]的最长公共子序列的长度。
从左到右，再从上到下计算矩阵dp
先计算第一行和第一列，再计算中间

  • str1[i] == str2[j]，dp[i][j] = dp[i-1][j-1]+1
  • str1[i] != str2[j]，dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

算出dp后，要根据dp找到公共子序列
1，从矩阵的右下角开始，有三种移动方式，向上、向左、 向左上。假设移动的过程中， i表
示此时的⾏数， j表示此时的列数，同时⽤⼀个变量res来表示最长公共子序列。
2，如果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， 然后向左上方移动。
3，如果dp[i][j]等于dp[i-1][j]，说明之前在计算dp[i][j]的时候， dp[i-1][j-1]+1这个决策不
是必须选择的决策，向上方移动即可。
4，如果dp[i][j]等于dp[i][j-1]，与步骤3同理，向左方移动。
5，如果dp[i][j]同时等于dp[i-1][j]和dp[i][j-1]，向上还是向下⽆所谓，选择其中⼀个即
可，反正不会错过必须选择的字符。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
public static int[][] getdp(char[] str1, char[] str2) {
	int[][] dp = new int[str1.length][str2.length];
	//初始化第一行
	for(int i = 0; i < str1.length; i++){
		if(str1[i]==str2[0]){
			dp[i][0] = 1;
			for(int j = i+1; j < str1.length; j++){
				dp[j][0] = 1;
			}
			break;
		}else{
			dp[i][0] = 0;
		}
		
	}
	//初始化第一列
	for(int i = 1; i < str2.length; i++){
		if(str1[0]==str2[i]){
			dp[0][i] = 1;
			for(int j = i+1; j < str2.length; j++){
				dp[0][j] = 1;
			}
			break;
		}else{
			dp[0][i] = 0;
		}
	}
	
	for(int i = 1; i < str1.length; i++){
		for(int j = 1;j < str2.length; j++){
			dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
			if(str1[i] == str2[j]){
				dp[i][j] = dp[i-1][j-1]+1;
			}
		}
	}
	
	return dp;
	}
public static char[] getAns(String str1, String str2){
	
	int m = str1.length()-1;
	int n = str2.length()-1;
	char[] char1 = str1.toCharArray();
	char[] char2 = str2.toCharArray();
	int[][] dp = getdp(char1, char2);
	int len = dp[m][n];
	char[] str = new char[len];
	while(len > 0){
		
		//m>0 和n>0放在最前面，因为有可能过界导致后面 dp[m][n] == dp[m][n-1]的判断不能进行
		if(n>0 && dp[m][n] == dp[m][n-1]){
			n--;
		}else if(m>0 && dp[m][n] == dp[m-1][n]){
			m--;
		}else{
			//dp[m][n] == dp[m-1][n-1]+1应该是一个判断分支，但是不能写出该判断条件
			//因为有可能到了第一行，m=0,无法计算m-1
			str[--len] = char1[m];
			m--;
			n--;
		}
	}
		
	return str; 
	
}