94、动态规划-最长公共子序列

1. 递归的基本思路：
   • 比较两个字符串的最后一个字符。如果相同，则这个字符一定属于最长公共子序列，然后在剩余的字符串上递归求解。
   • 如果最后一个字符不相同，则分两种情况递归求解：
     • 去掉 text1 的最后一个字符，保留 text2 的所有字符。
     • 去掉 text2 的最后一个字符，保留 text1 的所有字符。
   • 取两种情况的最大值作为最终结果。
2. 递归的终止条件：
   • 如果任一字符串为空，则公共子序列长度为0。

代码如下：

public class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        return lcs(text1, text2, text1.length(), text2.length());
    }
 
    private int lcs(String text1, String text2, int i, int j) {
        // 终止条件：任一字符串长度为0
        if (i == 0 || j == 0) {
            return 0;
        }
 
        // 递归计算
        if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
            // 最后一个字符相同，是LCS的一部分
            return 1 + lcs(text1, text2, i - 1, j - 1);
        } else {
            // 最后一个字符不同，选择不包含text1[i-1]或text2[j-1]的最大LCS
            return Math.max(lcs(text1, text2, i - 1, j), lcs(text1, text2, i, j - 1));
        }
    }
}

动态规划是优化递归的方法，使用表格来存储中间结果，避免重复计算。

1. 定义状态：

   • dp[i][j] 表示 text1[0...i-1] 和 text2[0...j-1] 的最长公共子序列的长度。

2. 状态转移方程：

   • 如果 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
   • 如果 text1[i-1] != text2[j-1]，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

3. 初始化：

   • 初始化 dp 数组，当 i 或 j 为0时，dp[i][j] = 0，表示一个字符串为空。

4. 填表顺序：

   • 由于每个 dp[i][j] 依赖于左边、上边和左上角的值，因此应从上到下、从左到右填表。

5. 返回结果：

   • dp[text1.length()][text2.length()] 即为两个字符串的最长公共子序列的长度。

代码如下：

public int longestCommonSubsequence(String text1, String text2) {
        // 获取输入字符串的长度
        int m = text1.length(), n = text2.length();
        
        // 创建动态规划表，多出的一行一列用于处理边界情况，即某一字符串长度为0的情况
        int[][] dp = new int[m + 1][n + 1];
        
        // 填充动态规划表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 检查当前位置的字符是否相同
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // 如果当前两个字符相同，那么这两个字符属于LCS的一部分
                    // 因此dp[i][j]等于左上角的值加1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 如果当前两个字符不相同，则LCS长度取决于不包含当前字符的子问题的最大值
                    // 即从左边或上边继承最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // 返回最终结果，即整个字符串的最长公共子序列长度
        return dp[m][n];
    }