两子串的公共子序列

两子串的公共子序列，子序列的问题难比子串，暴力也难搞，动态规划大法好，
1.确定dp[i][j]：dp[i][j]表示字符串str1的[0,i]和str2的[0,j]的最大公共子序列
2.填已经确定的dp值，这里是第一行str1的[0,n1]和str2的[0]的最大公共子序列，第一列str1的[0]和str2的[0,n2]的最大公共子序列，
3.找递归关系，根据已知求未知，dp[i][j]可能来自三个方向，左上方dp[i-1][j-1]，上方dp[i-1][j],左方dp[i-1][j]，选择三者最大值，想不明白的话真的难啊
4.dp[n1][n2]的返回的是str1和str2这道题要返回公共子序列，需要根据dp表倒推从dp[0][0]到dp[n1][n2]的路径

// 时间复杂度O(M*N)，空间复杂度
public class ComSubSequence {
	public int[][] getDp(String str1, String str2) {
		int m = str1.length(), n = str2.length();
		char[] s1 = str1.toCharArray(), s2 = str2.toCharArray();
		int[][] dp = new int[m][n];
		dp[0][0] = s1[0] == s2[0] ? 1 : 0;// 如果两个字符串的首字母相等，则
		for (int i = 1; i != m; i++) {// 列表示str1的变化范围，只跟str2[0]比较，第一列最大可能值是1
			dp[i][0] = dp[i - 1][0] == 1 || s1[i] == s2[0] ? 1 : 0;
		}
		for (int i = 1; i != n; i++) {// 行表示str2的变化范围，只跟str1[0]比较，第一行最大可能值是1，
			dp[0][i] = dp[0][i - 1] == 1 || s2[i] == s1[0] ? 1 : 0;
		}
		for (int i = 1; i != m; i++) {// 从dp[1][1]位置开始递推
			for (int j = 1; j != n; j++) {
				dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				dp[i][j] = s1[i] == s2[j] ? dp[i - 1][j - 1] + 1 : dp[i][j];
			}
		}
		return dp;
	}

	public String lcse(String str1, String str2) {
		// 根据dp表找路径，与构建dp时相反，从左往右，从上往下来到dp[i][j]的方向有3个，从左过来的，从上过来的，从左上角过来
		int m = str1.length() - 1, n = str2.length() - 1;
		int[][] dp = getDp(str1, str2);
		char[] res = new char[dp[m][n]];//最大公共串长度为dp[m][n],申请辅助数组，存公共串
		int index = res.length - 1;
		while (index >= 0) {// 这个根据长度找路径还是挺陌生的
			if (m > 0 && dp[m][n] == dp[m - 1][n]) {// 从上方来的,str1[0,m]和str2[0,n]的最长子串等于str1[0,m-1]
				m--;
			} else if (n > 0 && dp[m][n] == dp[m][n - 1]) {// 从左方来的,str1[0,m]和str2[0,n]的最长子串等于str1[0,m-1]
				n--;
			} else {// 当前位置是两者的公共部分
				res[index--] = str1.charAt(m);// ==str2.charAt(n)
				m--;
				n--;
			}
		}
		return String.valueOf(res);
	}

	public static void main(String[] args) {
		String str1 = "A1BC2D3EFGH45I6JK7L8M9N", str2 = "12OPQ3RST4U5V6W7XYZ89";
		ComSubSequence cs = new ComSubSequence();
		String res = cs.lcse(str1, str2);
		System.out.println(res);
	}

}