动态规划详解：最长公共子序列问题的高效解法

在编程中，子序列问题经常出现，并且它们涉及到字符串的处理与算法优化。今天我们来探讨一个经典的算法问题：最长公共子序列（Longest Common Subsequence，LCS）。这一问题不仅是面试中的高频考题，也是动态规划的典型应用场景。本文将详细介绍这个问题的解决方案，特别是如何使用动态规划来有效求解。

1. 问题描述

最长公共子序列问题要求在给定的两个字符串中找到它们的最长公共子序列。子序列的定义是从一个字符串中删除部分字符（也可以不删除），并保持字符的相对顺序，生成的新字符串。因此，最长公共子序列是指两个字符串中的最长的相同子序列。

示例

• 示例 1
  输入：text1 = "abcde"，text2 = "ace"
  输出：3
  解释："ace" 是 text1 和 text2 的最长公共子序列，长度为 3。

• 示例 2
  输入：text1 = "abc"，text2 = "abc"
  输出：3
  解释：最长公共子序列是 "abc"，长度为 3。

• 示例 3
  输入：text1 = "abc"，text2 = "def"
  输出：0
  解释：两个字符串没有公共子序列，因此返回 0。

1143. 最长公共子序列 - 力扣（LeetCode）

2. 动态规划解法

2.1 动态规划的核心思想

动态规划（Dynamic Programming）是解决最优化问题的一种有效方法，核心思想是通过拆解子问题并存储子问题的结果，避免重复计算。对于最长公共子序列问题，我们可以通过逐步构建子问题的解来得到整个问题的解。

2.2 最优子结构

最长公共子序列问题具有最优子结构，这意味着更大的问题可以由较小的子问题递归地解决。具体而言：

• 如果 text1[i-1] == text2[j-1]，那么最长公共子序列的长度可以从两个字符串都去掉最后一个字符后的最长公共子序列长度加 1 得到。
• 如果 text1[i-1] != text2[j-1]，则最长公共子序列应该是去掉 text1 的最后一个字符或者去掉 text2 的最后一个字符后的两个子问题的最大值。

2.3 状态定义

我们可以定义一个二维数组 dp，其中 dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列的长度。

2.4 状态转移方程

根据最优子结构性质，状态转移方程可以表示为：

$$dp[i][j]=\{\begin{array}{ll}dp[i-1][j-1]+1,& \text{if }text1[i-1]==text2[j-1]\\ \max (dp[i-1][j],dp[i][j-1]),& \text{if }text1[i-1]\ne text2[j-1]\end{array}$$

• 当两个字符串的最后一个字符相同时，当前最长公共子序列的长度等于去掉最后一个字符后子问题的长度加 1。
• 如果最后一个字符不相同，则取两个较小子问题的最大值。

2.5 初始条件

当 i == 0 或 j == 0 时，即其中一个字符串为空时，最长公共子序列的长度为 0，因此有：

$$dp[0][j]=dp[i][0]=0$$

2.6 代码实现

#include <iostream>
#include <vector>
using namespace std;

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length();
    int n = text2.length();
    
    // 创建 dp 数组，dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列长度
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // 填充 dp 数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                // 如果最后一个字符相同，公共子序列长度加1
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // 如果最后一个字符不同，取两个可能的子问题中的较大值
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    // dp[m][n] 就是两个字符串的最长公共子序列长度
    return dp[m][n];
}

int main() {
    string text1 = "abcde";
    string text2 = "ace";
    cout << "最长公共子序列的长度: " << longestCommonSubsequence(text1, text2) << endl;
    return 0;
}

2.7 示例讲解

示例 1：

输入：text1 = "abcde"，text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。

DP数组计算过程：

从表格可以看出，dp[5][3] = 3，即 text1 = "abcde" 和 text2 = "ace" 的最长公共子序列长度为3。

示例 2：

输入：text1 = "abc"，text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。

DP数组计算过程：

这里，text1 和 text2 是完全相同的，因此最长公共子序列是 "abc"，长度为 3。

示例 3：

输入：text1 = "abc"，text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。

DP数组计算过程：

从表格可以看出，dp[3][3] = 0，即没有公共子序列。

3. 递归解法（带备忘录）

递归解法虽然直观易懂，但直接递归会导致大量重复计算。为避免这种重复计算，我们可以使用备忘录来存储已经计算过的子问题的结果，从而提高效率。

3.1 递归代码实现

#include <iostream>
#include <vector>
using namespace std;

int dfs(string& text1, string& text2, int i, int j, vector<vector<int>>& memo) {
    // 如果 i 或 j 小于 0，说明已经到达字符串的边界，返回 0
    if (i < 0 || j < 0) {
        return 0;
    }
    // 如果已经计算过这个子问题，直接返回备忘录中的结果
    if (memo[i][j] != -1) {
        return memo[i][j];
    }
    // 如果最后一个字符相同，递归求解并加1
    if (text1[i] == text2[j]) {
        memo[i][j] = dfs(text1, text2, i - 1, j - 1, memo) + 1;
    } else {
        // 如果最后一个字符不同，选择去掉一个字符的两个子问题的较大值
        memo[i][j] = max(dfs(text1, text2, i - 1, j, memo), dfs(text1, text2, i, j - 1, memo));
    }
    return memo[i][j];
}

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length();
    int n = text2.length();
    // 初始化 memo 数组，-1 表示还没有计算过
    vector<vector<int>> memo(m, vector<int>(n, -1));
    return dfs(text1, text2, m - 1, n - 1, memo);
}

int main() {
    string text1 = "abcde";
    string text2 = "ace";
    cout << "最长公共子序列的长度: " << longestCommonSubsequence(text1, text2) << endl;
    return 0;
}

4. 总结

• 动态规划是解决最长公共子序列问题的最优解法，时间复杂度为 O(m * n)，空间复杂度也是 O(m * n)。通过二维数组存储子问题的解，可以避免大量的重复计算。
• **递归法（带备忘录）**也是一种可行的方案，它通过递归来逐步求解子问题，使用备忘录存储中间结果，从而避免重复计算，时间复杂度同样为 O(m * n)。

总体而言，动态规划是一种更加直观、效率高的解法，对于初学者来说也是更容易掌握的。