C++实现最长公共子序列(LCS)：动态规划算法详解

晚来风

发布时间：2026-10-15| 5人浏览过

原创

本文介绍如何使用C++结合动态规划技术高效解决最长公共子序列（LCS）问题。文章拆解了二维状态表的构建逻辑与路径回溯过程，提供可直接运行的完整代码示例，并分析了时间空间复杂度。

算法核心原理

最长公共子序列（Longest Common Subsequence, LCS）旨在找出两个字符串中共同拥有的、长度最长的子序列。该问题不适合使用贪心算法，因为局部最优选择往往导致全局非最优，而动态规划可以通过记录子问题的解来避免重复计算。

算法依赖两个关键矩阵：

长度矩阵 (num)：num[i][j] 表示字符串A的前i个字符与字符串B的前个字符的LCS长度。
方向标记矩阵 (flag)：用于回溯构造具体的子序列。
- 1：对角线方向，表示 A[i-1] == B[j-1]，当前字符匹配成功，纳入子序列。
- 2：水平向左，表示从左侧转移而来，B[j-1] 未匹配或无需考虑。
- 3：竖直向上，表示从上方转移而来，A[i-1] 未匹配或无需考虑。

C++ 代码实现

以下代码实现了完整的动态规划填表与逆推打印功能。代码中使用全局数组简化内存管理，并在主函数中演示了标准用法。

#include <stdio.h>
#include <string.h>

// 定义最大字符串长度，根据实际项目需求调整
#define MAX_LEN 500

char a[MAX_LEN], b[MAX_LEN];
int num[MAX_LEN + 1][MAX_LEN + 1]; // 记录LCS长度的中间结果
int flag[MAX_LEN + 1][MAX_LEN + 1]; // 标记数组：1-斜向(匹配), 2-向右, 3-向下

void LCS();       // 核心动态规划求解
void getLCS();    // 逆向追踪并输出子序列

int main()
{
    // 初始化测试数据
    strcpy(a, "ABCBDAB");
    strcpy(b, "BDCABA");
    
    // 清零数组，防止干扰
    memset(num, 0, sizeof(num));
    memset(flag, 0, sizeof(flag));
    
    // 执行算法
    LCS();
    
    // 输出LCS长度
    printf("LCS Length: %d\n", num[strlen(a)][strlen(b)]);
    
    // 输出具体的LCS字符串
    printf("LCS Sequence: ");
    getLCS();
    printf("\n");
    
    return 0;
}

void LCS()
{
    int lenA = strlen(a);
    int lenB = strlen(b);
    
    for (int i = 1; i <= lenA; i++)
    {
        for (int j = 1; j <= lenB; j++)
        {
            // 注意：数组下标从1开始，对应字符串下标需减1
            if (a[i - 1] == b[j - 1]) 
            {
                num[i][j] = num[i - 1][j - 1] + 1;
                flag[i][j] = 1; // 匹配成功，记录对角线方向
            }
            else if (num[i][j - 1] > num[i - 1][j])
            {
                num[i][j] = num[i][j - 1];
                flag[i][j] = 2; // 来自左侧
            }
            else
            {
                num[i][j] = num[i - 1][j];
                flag[i][j] = 3; // 来自上方
            }
        }
    }
}

void getLCS()
{
    char res[MAX_LEN];
    int i = strlen(a);
    int j = strlen(b);
    int k = 0; // 结果数组指针
    
    while (i > 0 && j > 0)
    {
        if (flag[i][j] == 1)
        {
            // 匹配字符，加入结果栈（注意顺序是逆序的）
            res[k++] = a[i - 1];
            i--;
            j--;
        }
        else if (flag[i][j] == 2)
        {
            j--; // 向左移动
        }
        else
        {
            i--; // 向上移动
        }
    }
    
    // 逆序打印得到正序结果
    for (int p = k - 1; p >= 0; p--)
    {
        printf("%c", res[p]);
    }
}