[数据结构与算法] 最长公共子序列（动态规划）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 最长公共子序列（动态规划） -> 正文阅读

[数据结构与算法]最长公共子序列（动态规划）

最长公共子序列（动态规划）

设 $X=\{A,B,C,B,D,A,B\}$ ， $Y=\{B,D,C,A,B,A\}$ ，则类似于序列 ${B,C,A\}$ 和 ${B,C,B,A\}$ 这样的子序列，它既是 $X$ 的子序列又是 $Y$ 的子序列，称为 $X$ 和 $Y$ 的公共子序列。本问题是求两个串的最长公共子序列，即求解所有公共子序列中最长的序列。

思路分析：

此问题满足动态规划的两个条件：最优子结构条件（最优解包含子问题最优解）和子问题重叠条件（计算过程中有重叠）。

设 $X[1:m]=\{x_1,x_2,...,x_m\}$ ， $Y[1:n]=\{y_1,y_2,...,y_n\}$ ，最长公共子序列 ${ } Z=\{\}$ 。

如果 $x_i=y_j$ ， $z_k=x_i=y_i$ 。子问题转化为求解 $X [i + 1 : m]$ 和 $Y [j + 1 : n]$ 的最长公共子序列。
如果 $x_i \neq y_j$ 。子问题转化为求解 $X [i + 1 : m]$ 和 $Y [j : n]$ 的最长公共子序列和求解 $X [i : m]$ 和 $Y [j + 1 : n]$ 的最长公共子序列。

进一步的，设 $L C S L [i] [j]$ 为 $X [i : m]$ 和 $Y [j : n]$ 的最长公共子序列的长度。

如果 $i = 0$ 或 $j = 0$ ， $L C S L [i] [j] = 0$ ；
如果 $x_i=y_j$ ， $L C S L [i] [j] = L C S L [i ? 1] [j ? 1] + 1$ ；
如果 $x_i \neq y_j$ ， $L C S L [i] [j] = m a x (L C S L [i ? 1] [j], L C S L [i] [j ? 1])$ 。

代码实现：

#include <stdio.h>

int **get2dZerosMatrix(int m, int n)
{
    int **matrix = new int *[m];
    for (int i = 0; i < m; i++)
    {
        matrix[i] = new int[n]{0};
    }
    return matrix;
}

void print2dMatrix(int **matrix, int m, int n)
{
    for (int i = 1; i < m; i++)
    {
        for (int j = 1; j < n; j++)
        {
            printf("%10d", matrix[i][j]);
        }
        printf("\n");
    }
}

void LCSLength(char *x, char *y, int m, int n, int **memtable, int **postable)
{
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            memtable[i][j] = 0;
            postable[i][j] = 0;
        }
    }
    for (int i = 1; i < m; i++)
    {
        for (int j = 1; j < n; j++)
        {
            if (x[i - 1] == y[j - 1])
            {
                memtable[i][j] = memtable[i - 1][j - 1] + 1;
                postable[i][j] = 1;
                continue;
            }
            if (memtable[i][j - 1] < memtable[i - 1][j])
            {
                memtable[i][j] = memtable[i - 1][j];
                postable[i][j] = 2;
            }
            else
            {
                memtable[i][j] = memtable[i][j - 1];
                postable[i][j] = 3;
            }
        }
    }
}

void LCS(int i, int j, char *x, int **postable)
{
    if (i == 0 || j == 0)
        return;
    if (postable[i][j] == 1)
    {
        LCS(i - 1, j - 1, x, postable);
        printf("%c", x[i - 1]);
    }
    else if (postable[i][j] == 2)
    {
        LCS(i - 1, j, x, postable);
    }
    else
    {
        LCS(i, j - 1, x, postable);
    }
}

int main()
{
    char x[] = {'A', 'B', 'C', 'B', 'D', 'A', 'B'};
    char y[] = {'B', 'D', 'C', 'A', 'B', 'A'};
    int m = sizeof(x) / sizeof(char) + 1, n = sizeof(y) / sizeof(char) + 1;
    int **memtable = get2dZerosMatrix(m, n);
    int **postable = get2dZerosMatrix(m, n);
    LCSLength(x, y, m, n, memtable, postable);
    printf("memtalbe\n");
    print2dMatrix(memtable, m, n);
    printf("postable\n");
    print2dMatrix(postable, m, n);
    LCS(m - 1, n - 1, x, postable);
    return 0;
}

在这里插入图片描述
备忘录方法

int lcslength_recur(char *x, char *y, int i, int j, int **memtable, int **postable)
{
    if (i == 0 || j == 0)
        return 0;
    if (memtable[i][j] > 0)
        return memtable[i][j];
    if (x[i - 1] == y[j - 1])
    {
        memtable[i][j] = 1 + lcslength_recur(x, y, i - 1, j - 1, memtable, postable);
        postable[i][j] = 1;
        return memtable[i][j];
    }

    int xpre = lcslength_recur(x, y, i - 1, j, memtable, postable);
    int ypre = lcslength_recur(x, y, i, j - 1, memtable, postable);

    if (ypre < xpre)
    {
        memtable[i][j] = xpre;
        postable[i][j] = 2;
    }
    else
    {
        memtable[i][j] = ypre;
        postable[i][j] = 3;
    }        

    return memtable[i][j];
}

int LCSLength(char *x, char *y, int m, int n, int **memtable, int **postable)
{
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            memtable[i][j] = 0;
            postable[i][j] = 0;
        }
    }
    return lcslength_recur(x, y, m - 1, n - 1, memtable, postable);
}