深入解析最短公共超序列：从递归到动态规划的演进之路

2026-02-03 22:29:28 0条评论 4次阅读 0人点赞

在这篇文章中，我们将一起攻克一个经典的算法难题：最短公共超序列（Shortest Common Supersequence, 简称 SCS）。如果你正在准备技术面试，或者纯粹对算法优化感兴趣，这篇文章正是为你准备的。我们将从最直观的递归思路出发，一步步发现性能瓶颈，进而引入动态规划进行优化，最终不仅求出超序列的长度，还会深入探讨如何还原出这个具体的字符串。

你将学会如何识别问题中的重叠子问题，如何用空间换时间，以及如何通过最长公共子序列（LCS）来简化思考过程。让我们开始这段算法探索之旅吧！

问题定义

首先，让我们明确一下目标。给定两个字符串 INLINECODEc71f0f44 和 INLINECODE5f4562b7，我们需要找到最短的字符串，使得 INLINECODE035b2ed8 和 INLINECODEed93a30f 都是这个新字符串的子序列。

什么是子序列？

简单来说，如果你可以从一个字符串中删除零个或多个字符（不改变剩余字符的相对顺序）得到另一个字符串，后者就是前者的子序列。例如，"ace" 是 "abcde" 的子序列。

直观分析

为了构建包含 INLINECODE88d8acf4 和 INLINECODEdd960eaa 的最短字符串，我们可以想象自己在合并这两个字符串。

  • 最笨的方法：直接把 INLINECODE6971e4a5 拼接到 INLINECODE8c3e1231 后面。这肯定能包含两者，但长度是 m + n。这太长了，因为它忽略了两者可能存在的公共部分。
  • 优化思路：如果 INLINECODE456e7733 和 INLINECODEb0374ce4 有相同的字符，且在合并时这些字符处于相同的相对位置，我们就应该只保留一份。这正是解决这个问题的核心——找到两者的公共部分，去除重复计算。

核心公式推导

假设我们正在处理字符串的末尾，设 INLINECODEa2c55860 和 INLINECODE1d2aec27 分别是当前 INLINECODE5cde1056 和 INLINECODE8273c3d7 的长度。我们的目标是计算 SCS(m, n)。

  • 字符匹配：

如果 INLINECODE33ac5ed3，这个字符显然在最终的超序列中只需要出现一次。我们只需要知道剩下的部分 INLINECODEb184b8ad 是多长，然后加 1 即可。

SCS(m, n) = 1 + SCS(m-1, n-1)

  • 字符不匹配：

如果 INLINECODEe0418c35，我们必须做出选择。我们要么保留 INLINECODEa4f1e8c0 的最后一个字符，要么保留 s2 的最后一个字符（或者两者都保留，但在计算长度时，为了最短，我们每次只能尝试移动一个指针）。我们要找的是这两条路径中最短的那条。

SCS(m, n) = 1 + min( SCS(m-1, n), SCS(m, n-1) )

方法一：朴素递归法

让我们先用最直接的递归代码来实现上述逻辑。这种方法思路清晰，但效率较低。

#include 
#include 
#include 
#include 
using namespace std;

/**
 * 朴素递归解法：计算最短公共超序列的长度
 * 
 * @param s1 第一个字符串
 * @param s2 第二个字符串
 * @param m s1 的当前处理长度
 * @param n s2 的当前处理长度
 * @return 超序列的长度
 */
int scsRecursion(string& s1, string& s2, int m, int n) {
    // 基础情况：如果其中一个字符串处理完了，
    // 超序列的长度就是另一个字符串剩余的长度
    if (m == 0) return n;
    if (n == 0) return m;

    // 如果末尾字符匹配，完美！我们只需要加 1，并继续处理前面的部分
    if (s1[m - 1] == s2[n - 1]) {
        return 1 + scsRecursion(s1, s2, m - 1, n - 1);
    } else {
        // 如果不匹配，我们有两种选择：
        // 1. 舍弃 s1 的末尾字符 (结果 +1，处理 s1[:m-1] 和 s2[:n])
        // 2. 舍弃 s2 的末尾字符 (结果 +1，处理 s1[:m] 和 s2[:n-1])
        // 我们取两者中较短的那个
        return 1 + min(scsRecursion(s1, s2, m - 1, n),
                       scsRecursion(s1, s2, m, n - 1));
    }
}

// 封装函数，方便调用
int getSuperSeqLen(string s1, string s2) {
    return scsRecursion(s1, s2, s1.length(), s2.length());
}

复杂度分析：

你会发现，虽然代码能跑通，但随着字符串长度增加，运行时间会呈指数级增长。时间复杂度为 $O(2^{(m+n)})$，空间复杂度为 $O(m+n)$（递归栈深度）。

为什么会这么慢？

让我们画一个简单的递归树。对于 INLINECODE1b1091c7，我们会计算 INLINECODE221f0224 的子问题。随后，当我们沿着不同的分支递归时，可能会再次遇到 ("A", "C") 并重新计算一遍。这种重叠子问题的大量重复计算是指数级爆炸的元凶。

方法二：记忆化搜索（自顶向下动态规划）

为了解决重复计算的问题，一个非常自然的想法是：拿一个本子记下来。一旦我们算出了某个 (m, n) 对应的结果，就把它存起来。下次再遇到这个状态时，直接查表，不再递归。这就是记忆化搜索。

#include 
#include 
#include 
#include 
using namespace std;

/**
 * 记忆化搜索解法
 * 使用二维数组 dp 记录已经计算过的状态
 */
int scsMemoUtil(string& s1, string& s2, int m, int n, vector<vector>& dp) {
    // 基础情况
    if (m == 0) return n;
    if (n == 0) return m;

    // 查表：如果已经计算过，直接返回
    if (dp[m][n] != -1) {
        return dp[m][n];
    }

    // 逻辑与递归法相同，但在返回前将结果存入 dp 表
    if (s1[m - 1] == s2[n - 1]) {
        dp[m][n] = 1 + scsMemoUtil(s1, s2, m - 1, n - 1, dp);
    } else {
        dp[m][n] = 1 + min(scsMemoUtil(s1, s2, m - 1, n, dp),
                           scsMemoUtil(s1, s2, m, n - 1, dp));
    }

    return dp[m][n];
}

int getSuperSeqLenMemo(string s1, string s2) {
    int m = s1.length();
    int n = s2.length();
    
    // 初始化 DP 表，-1 表示未计算
    vector<vector> dp(m + 1, vector(n + 1, -1));
    
    return scsMemoUtil(s1, s2, m, n, dp);
}

复杂度分析：

通过引入 dp 数组，我们将时间复杂度降到了 $O(m \times n)$，因为我们只计算了每一个子问题一次。空间复杂度主要是递归栈的深度和 DP 表的大小，即 $O(m \times n)$。

方法三：自底向上动态规划（表格式解法）

虽然记忆化搜索很不错，但在实际工程中，为了避免递归带来的栈溢出风险（特别是在处理超长字符串时），我们更倾向于使用迭代的方式。这就是自底向上的动态规划。

我们将构建一个二维表格，从空字符串开始，逐步填表直到 (m, n)。

#include 
#include 
#include 
#include 
using namespace std;

/**
 * 自底向上动态规划解法（推荐）
 * 迭代填充 dp 表
 */
int getSuperSeqLenDP(string s1, string s2) {
    int m = s1.length();
    int n = s2.length();

    // 创建 DP 表
    // dp[i][j] 代表 s1[0...i-1] 和 s2[0...j-1] 的最短超序列长度
    vector<vector> dp(m + 1, vector(n + 1));

    // 初始化第一列：s2 为空，SCS 长度等于 s1 当前长度
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }

    // 初始化第一行：s1 为空，SCS 长度等于 s2 当前长度
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;
    }

    // 填充表格的其余部分
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            
            // 注意：字符串下标从 0 开始，所以用 i-1 和 j-1
            if (s1[i - 1] == s2[j - 1]) {
                // 字符匹配，取左上角的值 + 1
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                // 字符不匹配，取左边或上边的最小值 + 1
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // 右下角的值即为最终答案
    return dp[m][n];
}

进阶思考：利用最长公共子序列 (LCS)

这里有一个非常有趣的性质，可以帮助我们秒解这道题的长度问题。

我们之前提到，SCS 的本质是 INLINECODE1b5d8dd9 + INLINECODEb6edbfaa 去除公共部分。更准确地说：

SCS 的长度 = (m + n) - LCS 的长度

为什么？因为 LCS（最长公共子序列）代表了两个字符串中最长的重叠部分。我们在合并时，这部分只算一次，所以总长度就是两者之和减去这部分的长度。

如果你对计算 LCS 很熟悉，可以直接套用 LCS 的代码，最后用 m + n - lcs 即可。这在空间优化上非常有用。

终极挑战：还原超序列字符串

面试官通常不会只让你求长度，接着会问："那怎么打印出这个最短的字符串呢？"

这其实比单纯求长度要稍微复杂一点，但我们可以利用刚才填充好的 INLINECODE2432cbe3 表，从 INLINECODEdb433ae2 开始倒推回去。

#include 
#include 
#include 
#include 
using namespace std;

/**
 * 构建并返回最短公共超序列字符串
 */
string printShortestSuperSeq(string s1, string s2) {
    int m = s1.length();
    int n = s2.length();

    // 1. 首先构建 DP 表（代码逻辑与求长度相同）
    vector<vector> dp(m + 1, vector(n + 1));

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j  0 && j > 0) {
        // 如果当前字符匹配
        if (s1[i - 1] == s2[j - 1]) {
            // 把这个字符加入结果
            result.push_back(s1[i - 1]);
            i--;
            j--;
        } 
        // 如果不匹配
        else {
            // 看 DP 表，上面的小还是左边的小？
            // 我们要向数值较大的方向移动（因为那是包含当前字符的路径）
            // 或者更简单地说：向 dp[i-1][j] 和 dp[i][j-1] 中较大的那个移动
            if (dp[i - 1][j] > dp[i][j - 1]) {
                result.push_back(s1[i - 1]);
                i--; // 移动到上方（相当于处理了 s1 的当前字符）
            } else {
                result.push_back(s2[j - 1]);
                j--; // 移动到左方（相当于处理了 s2 的当前字符）
            }
        }
    }

    // 3. 处理剩余字符
    // 如果循环结束后 s1 还有剩余
    while (i > 0) {
        result.push_back(s1[i - 1]);
        i--;
    }
    // 如果循环结束后 s2 还有剩余
    while (j > 0) {
        result.push_back(s2[j - 1]);
        j--;
    }

    // 4. 反转字符串
    reverse(result.begin(), result.end());

    return result;
}

常见错误与调试建议

在实现上述算法时，你可能会遇到一些坑，这里有几个提示供你参考：

  • 字符串下标错位：最容易犯的错误是混淆字符串的索引 INLINECODE2d936d31（从0开始）和 DP 表的索引 INLINECODEf87da163（代表前 i 个字符）。一定要记住 INLINECODE713de539 对应的是 INLINECODEef1ccd31 的状态。
  • 打印逻辑中的贪心选择：在回溯打印字符串时，当字符不匹配，我们应该向 INLINECODEe6b83fe2 还是 INLINECODEec859b61 移动？

* 正确的逻辑是：如果上方值 INLINECODE455bd9c2 左方值，说明当前 INLINECODEd3d64553 的字符是必须的（因为它在更长的路径上被选中了），向上移；反之向左移。如果两者相等，通常意味着两条路径都可以，选哪一条都行（但在具体字符选择上会决定最终输出的顺序）。

  • Java 中的输入处理：如果你在写 Java，要注意 Scanner 处理字符串时可能包含的换行符问题，最好使用 INLINECODE2c503afe 或按行读取后再 INLINECODEbec47f7d。

总结

我们今天深入探讨了最短公共超序列问题，从简单的 $O(2^n)$ 递归解法，优化到了 $O(m \times n)$ 的动态规划解法，甚至利用 LCS 的数学性质简化了计算。最后，我们还攻克了还原具体字符串的难关。

掌握这类问题的关键在于：识别状态、建立状态转移方程以及选择合适的优化手段（Memoization 或 Tabulation）。希望这篇深入的分析能帮助你在下次遇到类似问题时，能够从容应对，写出既高效又优雅的代码。

如果你觉得这篇文章对你有帮助，不妨试着自己动手实现一下这些代码，或者尝试解决它的变种问题（例如三个字符串的最短超序列）。祝编码愉快！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/23298.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年