题目
LeetCode原题—最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
暴力递归
这道题的模型是术语样本对应模型，根据给定的两个样本从尾部进行划分，列出每一种的可能性即可（别问为什么，问就是经验。。）。
暴力递归的整体思路是这样，求的是最长公共子序列，所以递归方法中返回从text1中 0 ~ i 和 text2中 0 ~ j 位置最长公共子序列的长度。
而给定的两个字符串中，返回的公共子序列中共有四种可能性，并在四种可能性中取最大值：
一共有这四种可能性，但是第四种没有必要进行比较。因为从上面四点的分析中可以看出：
5. 例子1中因为是可能会以text1[i]位置结尾，所以text[i]是不动的要保留，而一定不会以text2[j]结尾，所以text2[j]是无用的要砍掉。
所以例子1中的最长公共子序列的长度是 text1[ 0 ~ i ] 与 text2[ 0 ~ j - 1]范围中公共子序列的长度（后续递归）。
其中例子1和例子2，每次都会参与最长公共子序列的比较，而例子3，只有在text1[i] == text2[j]时，才会进行比较。
代码
public static int longestCommonSubsequence(String text1, String text2) {
if (text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) {
return 0;
}
char[] str1 = text1.toCharArray();
char[] str2 = text2.toCharArray();
return process(str1, str2, str1.length - 1, str2.length - 1);
}
//只看str1[0 ~ i] 位置 和 str2[0 ~ j]位置,返回最大公共子序列
//有几种可能性
//1.一定不会以str1[i] 位置结尾 但是可能会以str2[j]位置结尾
//2.一定不会以str2[j] 位置结尾 但是可能会以str1[i]位置结尾
//3.一定以str1[i]和str2[j]位置结尾
//4. 一定不以str[i]和str2[j]结尾
public static int process(char[] str1, char[] str2, int i, int j) {
if (i == 0 && j == 0) {
return str1[i] == str2[j] ? 1 : 0;
}
//此时 i 来到了最后一个字符
else if (i == 0) {
//如果此时 str1[i] 位置 == str2[j] 相等，说明有一个公共子序列
if (str1[i] == str2[j]) {
return 1;
} else {
//如果不相等， str2 去j - 1位置
return process(str1, str2, i, j - 1);
}
}
//此时 str2来到了最后一个字符
else if (j == 0) {
//此时 如果 str1[i] = str2[j] 相等，同样说明有一个公共子序列
if (str1[i] == str2[j]) {
return 1;
}else {
//否则 让 str1 去 i - 1位置继续递归
return process(str1, str2, i - 1, j);
}
}
//str1 和 str2 都没有到最后一个字符
else{
//一定不会以str1[i] 位置结尾 但是可能会以str2[j]位置结尾
int p1 = process(str1, str2, i - 1, j);
//一定不会以str1[j] 位置结尾 但是可能会以str1[i]位置结尾
int p2 = process(str1, str2, i, j - 1);
//一定以str1[i]和str2[j]位置结尾
int p3 = str1[i] == str2[j] ? 1 + process(str1, str2, i - 1, j - 1) : 0;
return Math.max(p1,Math.max(p2,p3));
}
}
动态规划
根据上面的暴力递归代码改写动态规划，根据可变参数 字符串长度 i 和 j 可确定dp表大小（str1.length * str2.length），根据base case可以进行dp表的初始化赋值操作，而代码中的依赖 ， 都是字符串长度 - 1 所以都是从0开始依赖。依赖的是 i - 1 ，j - 1和 i -1 j - 1。
代码
public static int dp(String s1, String s2) {
if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0) {
return 0;
}
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
int M = str1.length;
int N = str2.length;
int[][] dp = new int[M][N];
dp[0][0] = str1[0] == str2[0] ? 1 : 0;
for (int j = 1; j < N; j++) {
dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j - 1];
}
for (int i = 1; i < M; i++) {
dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
}
for (int i = 1; i < M; i++) {
for (int j = 1; j < N; j++) {
int p1 = dp[i - 1][j];
int p2 = dp[i][j - 1];
int p3 = str1[i] == str2[j] ?( 1 + dp[i - 1][j - 1]) : 0;
dp[i][j] = Math.max(p3, Math.max(p1, p2));
}
}
return dp[M - 1][N - 1];
}