动态规划算法是运筹学中求解多阶段决策问题的经典算法，本文将介绍动态规划算法的基本思想，并介绍如何使用动态规划算法求解最长公共子序列问题。

1. 动态规划算法的基本思想

动态规划算法本质也是基于分治思想，将待求解问题分解成若干个子问题。但是传统的分治法经分解得到的子问题往往不是相互独立的，因此在分治法求解的过程中有些子问题会被重复计算多次，这种冗余计算使得算法的时间复杂度增大。

那么我们很自然地会想到，可以用空间换时间，如果 把已解决的子问题的答案保存在表格中，再次需要时从表格中查找已经求解的答案，就可以避免大量的重复计算 ，这就是动态规划算法。

下面我们通过最长公共子序列问题的求解，进一步了解动态规划算法在实际应用中如何实现。

2. 最长公共子序列（LCS）问题

2.1 子序列定义

给定序列X={x1,x2,…,xm}X=\{x_1, x_2, … ,x_m\}X={x1​,x2​,…,xm​}，若序列Z={z1,z2,…,zk}Z=\{z_1, z_2, …, z_k\}Z={z1​,z2​,…,zk​}是XXX的子序列，则存在一个严格递增下标序列{i1,i2,…,ik}\{i_1, i_2, …, i_k\}{i1​,i2​,…,ik​}，使得对于所有j=1,2,…,kj=1, 2, … ,kj=1,2,…,k，有zj=xijz_j={x_i}_{j}zj​=xi​j​。

例如：序列Z={B，C，D，A}Z=\{B，C，D，A\}Z={B，C，D，A}是序列X={A，B，C，B，D，A，B}X=\{A，B，C，B，D，A，B\}X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，6}\{2，3，5，6\}{2，3，5，6}。

给定2个序列X={x1,x2,…,xm}X=\{x_1, x_2, … ,x_m\}X={x1​,x2​,…,xm​}和Y={y1,y2,…,yn}Y=\{y_1, y_2, … ,y_n\}Y={y1​,y2​,…,yn​}，若另一序列ZZZ既是XXX的子序列又是YYY的子序列，则称ZZZ是序列XXX和YYY的公共子序列，最大长度的ZZZ即为XXX和YYY的最长公共子序列（LCS）。

2.2 LCS的子问题与数据结构设计

求XXX和YYY的LCS可分解为2种情况：

  1. 如果xm=ynx_m=y_nxm​=yn​，那么求Xm−1X_{m-1}Xm−1​和Yn−1Y_{n-1}Yn−1​的LCS。
  2. 如果xm≠ynx_m \neq y_nxm​=yn​，那么求Xm−1X_{m-1}Xm−1​和YYY的LCS，求XXX和Yn−1Y_{n-1}Yn−1​的LCS，取两者中的最大的。

因此，将c[i, j]定义为XiX_iXi​和YjY_jYj​的LCS长度，i=0∼mi=0 \sim mi=0∼m，j=0∼nj=0 \sim nj=0∼n：

c[i][j]={0i=0,j=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]=\left\{\begin{matrix} 0 & i=0,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{matrix}\right.c[i][j]=⎩ ⎨ ⎧​0c[i−1][j−1]+1maxc[i][j−1],c[i−1][j]​i=0,j=0i,j>0;xi​=yj​i,j>0;xi​=yj​​

3. 程序代码

下面我们用C++对上述递归式进行代码实现，首先使用lcs.cpp找出一个LCS，在此基础上再扩展到lcs_all.cpp找出全部LCS。

3.1 lcs.cpp（找出一个LCS）

lcs.cpp按照《算法导论》一书上的伪代码改编而成，在书中伪代码的基础上，实现了不用表b，只用表c来完成找出最大公共子序列的任务。因为每个c[i][j]只依赖于c[i−1][j]、c[i][j−1]、c[i−1][j−1]三项，当给定c[i][j]时，我们可以在O(1)O(1)O(1)的时间内判定出c[i][j]是使用了三项中的哪一项。从而节约了Θ(mn)\Theta(mn)Θ(mn)的空间。需要注意的是：如果两个字符串存在多个LCS时，按照书中伪代码实现的lcs.cpp只能输出其中一个LCS。

//动态规划求解并输出其中一个LCS 
#include <iostream>
#include <string>

using namespace std;

int max(int a, int b) {  //返回a，b中值较大的元素 
	return (a > b) ? a : b;
}

int lcs_length(string sx, string sy, int **c) { //动态规划计算LCS的长度
	int xlen = sx.length();
	int ylen = sy.length();
	//c[i][j]记录sx[i]与sy[j]的LCS的长度  
	for (int i = 0; i < xlen + 1; i++) {
		for (int j = 0; j < ylen + 1; j++) {
			if (i == 0 || j == 0) {             //情形1：i = 0或j = 0; 
				c[i][j] = 0;
			}
			else if (sx[i - 1] == sy[j - 1]) { //情形2：i, j > 0且sx[i-1] = sy[j-1] 
				c[i][j] = c[i - 1][j - 1] + 1;	
			}
			else {                             //情形3：i, j > 0且sx[i-1] != sy[j-1] 
				c[i][j] = max(c[i][j - 1], c[i - 1][j]);
			}
		}
	}
	return c[xlen][ylen];
}

void print_lcs(int **c, string sx, int i, int j, string &s) { //递归将sx与sy的一个LCS赋值给字符串s 
	if (i == 0 || j == 0) {             //对应lcs_length()中的情形1 
		return;
	}	
	if (c[i][j] == c[i - 1][j]) {       //对应lcs_length()中的情形3 
		print_lcs(c, sx, i - 1, j, s);
	}
	else if (c[i][j] == c[i][j - 1]) {  //对应lcs_length()中的情形3  
		print_lcs(c, sx, i, j - 1, s);
	}
	else {                              //对应lcs_length()中的情形2 
		print_lcs(c, sx, i - 1, j - 1, s);
		s += sx[i - 1];
	}
}

int main() {
	string sx, sy;
	cout << "Please enter the string x and the string y:" << endl;
	cout << "sx: ";
	cin >> sx;
	cout << "sy: ";
	cin >> sy;
	int xlen = sx.length();
	int ylen = sy.length();
	int **c = new int *[xlen + 1];     //为动态规划表开空间 
	for (int i = 0; i < xlen + 1; i++) {
		c[i] = new int [ylen + 1];
	}
	int maxlen = lcs_length(sx, sy, c);
	cout << "The length of LCS is " << maxlen << endl;
	string s;
	print_lcs(c, sx, xlen, ylen, s);
	cout << "The LCS of sx and sy is: " << s << endl;
	for (int i = 0; i < xlen + 1; i++) { //释放占用的空间 
        delete[]c[i];
    }
    delete[]c;
	return 0;
}

3.2 lcs_all.cpp（找出全部LCS）

为了输出全部的LCS，我对lcs.cpp中的print_lcs函数进行了改进，改进后的代码见lcs_all.cpp。在lcs_all.cpp中，我从动态规划表右下角开始回溯，直到到达表的上边界或左边界停止。若sx[i-1]=sy[j-1]，则把这个字符放入最长公共子序列中；若sx[i-1] != sy[j-1]，则比较c[i-1][j]和c[i][j-1]的值，跳入值较大的继续进行判断；若c[i-1][j] == c[i][j-1]，说明最长公共子序列有多个，两边都要进行回溯。最后将所有的LCS都保存在set中。需要注意的是：当字符串过长时，由于回溯范围过广，输出全部的LCS耗时很长。

//动态规划求解并输出所有的LCS
#include <iostream>
#include <string>
#include <set>

using namespace std;

set<string> lcsSet;      //将所有的lcs保存在set中 

int max(int a, int b) {  //返回a，b中值较大的元素 
	return (a > b) ? a : b;
}

int lcs_length(string sx, string sy, int **c) { //动态规划计算LCS的长度
	int xlen = sx.length();
	int ylen = sy.length();
	//c[i][j]记录sx[i]与sy[j]的LCS的长度  
	for (int i = 0; i < xlen + 1; i++) {
		for (int j = 0; j < ylen + 1; j++) {
			if (i == 0 || j == 0) {             //情形1：i = 0或j = 0; 
				c[i][j] = 0;
			}
			else if (sx[i - 1] == sy[j - 1]) { //情形2：i, j > 0且sx[i-1] = sy[j-1] 
				c[i][j] = c[i - 1][j - 1] + 1;	
			}
			else {                             //情形3：i, j > 0且sx[i-1] != sy[j-1] 
				c[i][j] = max(c[i][j - 1], c[i - 1][j]);
			}
		}
	}
	return c[xlen][ylen];
}

string reverse(string s) { //将字符串s逆序 
	int low = 0;
	int high = s.length() - 1;
	while (low < high) {  
		char temp = s[low]; //交换字符串最低位和最高位 
		s[low] = s[high];
		s[high] = temp;
		low++;
		high--;
	}
	return s;
} 

void print_lcs(int **c, string sx, string sy, int i, int j, string s) { //根据动态规划表回溯 
	while (i > 0 && j > 0) {      //从动态规划表最右下角开始回溯，直至到达i或j小于等于0为止 
		if (sx[i - 1] == sy[j - 1]) { //若sx[i-1] == sy[j-1]，则把这个字符放入LCS中
			s += sx[i - 1];
			i--;
			j--;
		}
		else {  //若sx[i-1] != sy[j-1]，则比较c[i-1][j]和c[i][j-1]的值，跳入值较大的继续进行判断
			if (c[i - 1][j] > c[i][j - 1]) { 
				i--;
			}
			else if (c[i - 1][j] < c[i][j - 1]) {
				j--;
			}	
			else {  //若c[i-1][j] == c[i][j-1]，说明最长公共子序列有多个，两边都要进行回溯
				print_lcs(c, sx, sy, i-1, j, s);
				print_lcs(c, sx, sy, i, j-1, s);
				return;
			}
		}
	}
	lcsSet.insert(reverse(s)); //将字符串s逆序放入集合lcsSet中 
}


int main() {
	string sx, sy;
	cout << "Please enter the string x and the string y:" << endl;
	cout << "sx: ";
	cin >> sx;
	cout << "sy: ";
	cin >> sy;
	int xlen = sx.length();
	int ylen = sy.length();
	int **c = new int *[xlen + 1];     //为动态规划表开空间 
	for (int i = 0; i < xlen + 1; i++) {
		c[i] = new int [ylen + 1];
	}
	int maxlen = lcs_length(sx, sy, c);
	cout << "The length of LCS is " << maxlen << endl;
	string s;
	print_lcs(c, sx, sy, xlen, ylen, s);
	cout << "The LCS of sx and sy is: " << endl;
	set<string>::iterator iter = lcsSet.begin();
	for (; iter != lcsSet.end(); iter++) {
		cout << *iter << endl;
	}
	for (int i = 0; i < xlen + 1; i++) { //释放占用的空间 
        delete[]c[i];
    }
    delete[]c;
	return 0;
}

4. 运行结果

使用lcs.cpp与lcs_all.cpp时，用户需输入字符串sx和字符串sy，按下回车键，程序会输出sx和sy的LCS的长度以及LCS字符串。

4.1 lcs.cpp

  1. sx：ABCBDAB
    sy：BDCABA
    lcs：BCBA（长度为4）
    在这里插入图片描述

  1. sx：1A2C3D4B56
    sy：B1D23CA45B6A
    lcs：12C4B6（长度为6）
    在这里插入图片描述

  2. sx：aabbbbeeeeeeeeeeddddddkktylmnqqqqqqtiunmsfg
    sy：abeffffffffttttttkkkkddddddrsunnspqtrmma
    lcs：abeddddddnqtm（长度为13）
    在这里插入图片描述

4.2 lcs_all.cpp

  1. sx：ABCBDAB
    sy：BDCABA
    lcs：（长度为4）
    BCAB
    BCBA
    BDAB
    在这里插入图片描述

  2. sx：1A2C3D4B56
    sy：B1D23CA45B6A
    lcs：（长度为6）
    123456
    1234B6
    12C456
    12C4B6
    在这里插入图片描述

# 算法 # 动态规划 # c++
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

量化挑战赛冠军专访：4小时啃下W4A8量化，我靠的是这些经验

avatar 魔乐社区
cover

「极限压缩 量化未来」Modelers GeekDay上海站圆满落幕

avatar 魔乐社区
cover

替你试过了，消费级显卡可以跑的开源文生图SOTA模型，顶级渲染、高密度文本绘图

avatar 魔乐社区