网站导航
> 技术文档 > 【动态规划】最长公共子序列问题 C++_c++最长公共子序列

【动态规划】最长公共子序列问题 C++_c++最长公共子序列

网友: 技术文档 2025-07-30 14:08:38

问题描述

  • 子序列：序列Z是原序列X的子序列，当且仅当Z的元素在X中按严格递增的下标顺序出现（不要求连续）。例如X={A,B,C,B,D,A,B}中，Z={B,C,D,B}是子序列，对应X的下标2→3→5→7。
  • 公共子序列：若序列Z同时是X和Y的子序列，则称Z为X和Y的公共子序列

最长公共子序列问题要求给定两个序列X、Y，找出X、Y的最长公共子序列

问题分析

  1. 最长公共子序列的结构
    设序列X={x1,x2,......,xm}和Y={y1,y2,......,yn}的最长公共子序列为Z={z1,z2,......,zk}，则：
    （1）若xm=yn，则zk=xm=yn，且Z-zk是X-xm和Y-yn的最长公共子序列
    （2）若xm≠yn且zk≠xm，则Z是X-xm和Y的最长公共子序列
    （3）若xm≠yn且zk≠yn，则Z是X和Y-yn的最长公共子序列

由此可见，2个序列的最长公共子序列包含了这两个序列的前缀最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。

  1. 建立最优值的递归方程
    c[i][j]={0i=0 orj=0c[i−1][j−1]+1i,j>0; xi=yjmax⁡{c[i][j−1],c[i−1][j]}i,j>0; xi≠yjc[i][j] = \\begin{cases} 0 & i = 0 \\ or j = 0 \\\\c[i-1][j-1] + 1 & i, j > 0;\\ x_i = y_j \\\\\\max\\{c[i][j-1], c[i-1][j]\\} & i, j > 0;\\ x_i \\neq y_j \\end{cases}c[i][j]=⎩⎨⎧​0c[i−1][j−1]+1max{c[i][j−1],c[i−1][j]}​i=0 orj=0i,j>0; xi​=yj​i,j>0; xi​=yj​​
  2. 自底向上求最优值
    在子问题空间中，共有mn个不同的子问题

遍历整个子问题空间，计算并存储当前问题的解

void LcsLength(char x[], char y[], int m, int n,int **c, int **b) {for (int i = 0; i <= m; i++)c[i][0] = 0;for (int j = 0; j <= n; j++)c[0][j] = 0;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (x[i] == y[j]){c[i][j] = c[i - 1][j - 1] + 1;}else if (c[i - 1][j] > c[i][j - 1]){c[i][j] = c[i - 1][j];}else{c[i][j] = c[i][j - 1];}}}}
  1. 构造最优解

在上一步求最优值的时候，加入辅助信息表b,用于存储当前位置的值的来源
我们规定，
b[i][j]=1，表示c[i][j]=c[i-1][j-1]+1
b[i][j]=2，表示c[i][j]=c[i-1][j]
b[i][j]=3，表示c[i][j]=c[i][j-1]

加入辅助信息的LcsLength函数

void LcsLength(char x[], char y[], int m, int n,int **c, int **b) {for (int i = 0; i <= m; i++)c[i][0] = 0;for (int j = 0; j <= n; j++)c[0][j] = 0;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (x[i] == y[j]){c[i][j] = c[i - 1][j - 1] + 1;b[i][j] = 1;}else if (c[i - 1][j] > c[i][j - 1]){c[i][j] = c[i - 1][j];b[i][j] = 2;}else{c[i][j] = c[i][j - 1];b[i][j] = 3;}}}}

构造最优解

void LCS(int **b, int i,int j,char x[]) {if (i == 0 || j == 0)return;if (b[i][j] == 1){LCS(b, i - 1, j - 1,x);cout << x[i];}else if (b[i][j] == 2)LCS(b, i - 1, j, x);elseLCS(b, i, j - 1, x);}

实例

设两个序列
X={a,b,c,b,d,a,b}
Y={b,d,c,a,b,a}

可计算出如下的c[i][j]和b[i][j]
【动态规划】最长公共子序列问题 C++_c++最长公共子序列
【动态规划】最长公共子序列问题 C++_c++最长公共子序列

代码

#includeusing namespace std;void LCS(int b[][8], int i,int j,char x[]) {if (i == 0 || j == 0)return;if (b[i][j] == 1){LCS(b, i - 1, j - 1,x);cout << x[i];}else if (b[i][j] == 2)LCS(b, i - 1, j, x);elseLCS(b, i, j - 1, x);}void LcsLength(char x[], char y[], int m, int n,int c[][8], int b[][8]) {for (int i = 0; i <= m; i++)c[i][0] = 0;for (int j = 0; j <= n; j++)c[0][j] = 0;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (x[i] == y[j]){c[i][j] = c[i - 1][j - 1] + 1;b[i][j] = 1;}else if (c[i - 1][j] > c[i][j - 1]){c[i][j] = c[i - 1][j];b[i][j] = 2;}else{c[i][j] = c[i][j - 1];b[i][j] = 3;}}}}int main() {char x[8] = { \' \',\'a\',\'b\',\'c\',\'b\',\'d\',\'a\',\'b\' };char y[7] = { \' \',\'b\',\'d\',\'c\',\'a\',\'b\',\'a\' };int c[8][8];int b[8][8];int m = 7, n = 6;LcsLength(x, y, m, n, c, b);cout << \"最长公共子序列长度为\" << c[m][n] << endl;cout << \"最长公共子序列为:\";LCS(b, m, n, x);return 0;}

运行结果
【动态规划】最长公共子序列问题 C++_c++最长公共子序列

在这个问题中，最长公共子序列有多种情况，由于我们的规定，找到了bdab这种情况，如果更改我们的规定，令c[i - 1][j] > c[i][j - 1]时，c[i][j]=3,则会找到另一种子序列

优化
我们可以注意到，c数组中每个位置的值只于它左侧、上方、左上方这三个值有关，可以优化掉多余的空间开销；同样，b数组也可以优化掉，我们只用c数组就能确定当前值c[i][j]来自c[i-1][j-1]、c[i][j-1]、c[i-1][j]中的哪一个

乐拍网交易

网络标签：

相关问题