经典动态规划问题 - 最长公共子序列（LCS）

1. 问题描述

在计算机科学中，最长公共子序列（LCS）问题是一个非常经典的动态规划问题。给定两个字符串，我们需要求出它们的最长公共子序列。注意，这里的子序列不是子串，即字符可以不连续出现，但字符的相对顺序不能改变。

例如，对于字符串 A = "ABCBDAB" 和 B = "BDCABB"，它们的最长公共子序列是 "BCAB"，长度为4。

2. LCS 问题的最优子结构

LCS 问题具有最优子结构，也就是说，问题的最优解可以通过其子问题的最优解构建出来。为了理解这一点，我们需要定义状态和状态转移方程。

子问题的定义：

设 dp[i][j] 表示字符串 A 的前 i 个字符和字符串 B 的前 j 个字符的最长公共子序列的长度。

状态转移方程：

如果 A[i] == B[j]，说明这两个字符相同，最长公共子序列长度可以加1。此时，dp[i][j] = dp[i-1][j-1] + 1。
如果 A[i] != B[j]，则最长公共子序列的长度为去掉当前一个字符后的最长公共子序列长度，即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

通过这个状态转移方程，我们可以逐步求解出整个问题的最优解。

公式：

如果字符相等：
```
dp[i][j] = dp[i-1][j-1] + 1
```
如果字符不等：
```
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
```

3. 实现步骤与代码解析

步骤1：初始化二维 DP 数组

我们首先需要一个二维数组 dp，其中 dp[i][j] 存储的是字符串 A 的前 i 个字符和字符串 B 的前 j 个字符的最长公共子序列的长度。数组的大小为 (m+1) * (n+1)，其中 m 和 n 分别是两个字符串的长度。

步骤2：状态转移的递推过程

然后我们从 dp[1][1] 开始，按照状态转移方程逐步填充整个 dp 数组，直到计算出 dp[m][n]，即两个字符串的最长公共子序列的长度。

步骤3：获取 LCS 长度的最终解

最终的解存储在 dp[m][n] 中，它表示 A 和 B 的最长公共子序列的长度。

Java代码案例：

public class LCS {
    // 求解两个字符串的最长公共子序列
    public static int longestCommonSubsequence(String A, String B) {
        int m = A.length();
        int n = B.length();
        
        // 创建 dp 数组，dp[i][j] 表示 A[0...i-1] 和 B[0...j-1] 的 LCS 长度
        int[][] dp = new int[m + 1][n + 1];
        
        // 填充 dp 数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;  // 字符相等，LCS 长度加 1
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);  // 字符不等，取最大值
                }
            }
        }
        
        // 最终结果存储在 dp[m][n] 中
        return dp[m][n];
    }

    public static void main(String[] args) {
        String A = "ABCBDAB";
        String B = "BDCABB";
        
        System.out.println("最长公共子序列的长度是: " + longestCommonSubsequence(A, B));
    }
}

代码解析：

初始化二维数组 dp：我们创建了一个大小为 (m+1) * (n+1) 的二维数组 dp，并且初始化所有值为 0。dp[i][j] 存储的是 A[0...i-1] 和 B[0...j-1] 的最长公共子序列的长度。
状态转移：通过两个嵌套的循环，我们根据状态转移方程逐步填充 dp 数组。如果 A[i-1] == B[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1，否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
返回最终解：最终的最长公共子序列的长度存储在 dp[m][n] 中，我们返回这个值。