☆☆☆☆思路：Longest Common Sequence (LCS) 问题。要对两个字符串进行扫描，因此需要两个维度进行动态规划。
1. 状态的定义：dp[m][n] 表示 S1[0...m] 和 S2[0...n] 的最长公共子序列的长度。
2. 状态转移：每次对最新需要考虑的字符，s1[m] 和 s2[n]
① 如果s1[m] == s2[n]，则 dp[m][n] = 1 + dp[m-1][n-1]
②如果s1[m] ！= s2[n]，则 dp[m][n] = max {dp[m-1][n], dp[m][n-1]} （往前缩一个）
3. 初始化：对于dp矩阵(m*n)的第一列，需要注意一旦dp[i][0]被设置为1，那么之后的dp[i+1...m][0]也都为1； dp矩阵的第一行，同理。
4. 结果：从左到右，再从上到下计算dp矩阵，右下角的值即为所求。
代码1：
class Solution { public int longestCommonSubsequence(String text1, String text2) { // 状态的定义：dp[m][n]表示s1[0...m] 和 s2[0...n] 的最长公共子序列的长度 int m = text1.length(), n = text2.length(); int[][] dp = new int[m][n]; dp[0][0] = text1.charAt(0) == text2.charAt(0) ? 1 : 0; for (int i = 1; i < m; i++) { dp[i][0] = Math.max(dp[i-1][0], text1.charAt(i) == text2.charAt(0) ? 1 : 0); // 注意还需要考虑以前的 } for (int j = 1; j < n; j++) { dp[0][j] = Math.max(dp[0][j-1], text1.charAt(0) == text2.charAt(j) ? 1 : 0); // 注意还需要考虑以前的 } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (text1.charAt(i) == text2.charAt(j)) { dp[i][j] = dp[i-1][j-1] + 1; }else { dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); } } } return dp[m-1][n-1]; } }
代码2（如果只求长度，参考“矩阵的最小路径和”，空间复杂度可压缩为O(min{M, N})）：
class Solution { public int longestCommonSubsequence(String text1, String text2) { /** * 空间压缩： * 二维dp数组中每个格子内的值会依赖它的左边，上边和左上边，和其他的值无关。 * 而左上角的值有可能会被上一步计算的时候就被替换掉了，所以必须要先保存下来。 */ int m = text1.length(), n = text2.length(); int[] dp = new int[n]; // 初始化第一行 dp[0] = text1.charAt(0) == text2.charAt(0) ? 1 : 0; for (int j = 1; j < n; j++) { dp[j] = Math.max(dp[j-1], text1.charAt(0) == text2.charAt(j) ? 1 : 0); } for (int i = 1; i < m; i++) { // 单独算第一列 int pre = dp[0]; dp[0] = Math.max(dp[0], text1.charAt(i) == text2.charAt(0) ? 1 : 0); for (int j = 1; j < n; j++) { int temp = dp[j]; // dp[j] 这个值会被替换，所以替换之前要把他保存下来 if (text1.charAt(i) == text2.charAt(j)) { dp[j] = pre + 1; // 左上 }else { dp[j] = Math.max(dp[j-1], dp[j]); // 左 或者 上 } pre = temp; } } return dp[n-1]; } }
【举一反三】：除了求出最长公共子序列的长度，还需要会根据dp数组求出最长公共子序列是什么！-----------参考左神书P210
思路为根据dp状态还原出求解dp的过程，来自哪个策略就朝哪个方向移动。具体方法为：
1. 从dp矩阵右下角开始，有三种移动方式：向上，向左，向左上。设移动过程中， i 表示此时的行数， j 表示此时的列数，同时 res 表示最长公共子序列；
2. 如果 dp[i][j] 大于 dp[i-1][j] 和 dp[i][j-1]，说明之前在计算dp[i][j] 时，一定是选择了决策 dp[i-1][j-1] + 1，可以确定str[1]等于str[2]，并且这个字符一定属于最长公共子序列，放入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]，向上还是向下无所谓，选择其一即可， 反正不会错过必须选择的字符。
private String lcse(String s1, String s2) { if (s1 == null || s2 == null || s1.equals("") || s2.equals("")) { return ""; } int[][] dp = getdp(s1, s2); int m = s1.length() - 1, n = s2.length() - 1; char[] res = new char[dp[m][n]]; int index = res.length - 1; while (index >= 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--] = s1.charAt(m); m --; n --; } } return String.valueOf(res); } public int[][] getdp(String text1, String text2) { // 状态的定义：dp[m][n]表示s1[0...m] 和 s2[0...n] 的最长公共子序列的长度 int m = text1.length(), n = text2.length(); int[][] dp = new int[m][n]; dp[0][0] = text1.charAt(0) == text2.charAt(0) ? 1 : 0; for (int i = 1; i < m; i++) { dp[i][0] = Math.max(dp[i-1][0], text1.charAt(i) == text2.charAt(0) ? 1 : 0); } for (int j = 1; j < n; j++) { dp[0][j] = Math.max(dp[0][j-1], text1.charAt(0) == text2.charAt(j) ? 1 : 0); } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (text1.charAt(i) == text2.charAt(j)) { dp[i][j] = dp[i-1][j-1] + 1; }else { dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); } } } return dp; }
【复杂度分析】：总的时间复杂度为O(M*N)，空间复杂度为O(M*N)。 如果只求长度，空间复杂度可压缩为O(min{M, N})
1. 求dp矩阵的某个位置就是简单比较值，时间复杂度为O(1)，由于dp大小为M*N，所以求dp矩阵的时间复杂度为O(M*N)
2. 通过dp得到最长公共子序列的过程为O(M+N),因为向左最多移动N个位置，向上最多移动M个位置。
3. 因此，总的时间复杂度为O(M*N)