问题描述：求两个字符串的最长公共子序列。
思路：使用动态规划的思想，将问题分解为小的子问题。 假设两个字符串序列分别为：X{x0, x1, x2,......, xm}, Y{y0, y1, y2,......, yn}。从后往前比较字符。 如果xm == yn， 则这个字符就是子序列中的一个字符， LCS就是序列{x0, x1, x2,......, xm-1}和{y0, y1, y2,......, yn-1}的LCS加上xm（或yn）。 如果xm != yn, 则求序列{x0, x1, x2,......, xm-1}与{y0, y1, y2,......, yn}的LCS1，{x0, x1, x2,......xm}与{y0, y1, y2......, yn-1}的LCS2，所求的LCS = max{LCS1, LCS2}.
所以建立的动态规划的公式为
注：图片来自《算法导论》
我们可以通过填表格使问题的解决过程更清晰。
用二维数组length来储存LCS的值。
用二维数组state来储存计算LCS的过程
先将表格的第一行第一列全部设为0，这是为了给接下来求LCS的长度做准备。
BDCABA 0000000A0 B0 C0 B0 D0 A0 B0然后比较每一个字符，如果两个字符相同，则在该位置填上其斜上方数值+1（即第二个式子 c[i,j] = c[i-1,j-1]+1）；否则填其上方和左方的较大值(即第三个式子 c[i,j] = max{ c[i-1,j], c[i,j-1] }).这个填表的方式是根据公式来的。
表格完成。表格中的最右下角数据即为LCS的长度。
state数组中的值 ，0：斜上方，1：上方，-1：左方。在求length数组的时候，其实state的值就已经确定了，当我们使用第二个式子 c[i,j] = c[i-1,j-1]+1 时，state的值就是0，使用第三个式子 c[i,j] = max{ c[i-1,j], c[i,j-1] } 时，如果c[i-1,j] 较大，state的值就是1，否则是-1.
通过下图可以看出，只有当state的值为0时，该位置的字符才属于LCS （state的值也是根据公式得出的，当该字符属于LCS 时，就要判断{x0, x1, x2,......, xm-1}和{y0, y1, y2,......, yn-1}的LCS，state的值为0，对应的就是行数和列数都减一； 当该字符不属于LCS时，state的值根据max{LCS1, LCS2}来决定，如果LSC1较大，那么state就是-1，对应的就是列数减一，在{x0, x1, x2,......, xm-1}与{y0, y1, y2,......, yn}中求LCS，同理，如果LSC2较大，state就是1，对应的就是行数减一，在{x0, x1, x2,......xm}与{y0, y1, y2......, yn-1}中求LCS）.
注：图片来自《算法导论》
从后往前遍历state，当state中的值为0时，说明该字符属于LCS，将其压入栈中，为1，行数减一；为-1，列数减一。最后依次将字符弹出栈，得到的就是两个字符串的LCS.
源代码：
#include<iostream> #include<stack> #include<string> #include<cstring> using namespace std; /*Function:获得最长子序列及其长度 Param:str1, str2分别表示输入的字符串*/ void getLCS(string &str1, string &str2){ int m = str1.length() + 1; int n = str2.length() + 1; int length[m][n]; //该数组用来记录最大子序列的长度 int state[m][n]; //该数组存储每次字符串的匹配状态 memset( state, 100, sizeof(state) ); for(int i=0; i<m; i++){ //初始化第1列 length[i][0] = 0; } for(int j=0; j<n; j++){//初始化第1行 length[0][j] = 0; } for(int i=1; i<m; i++){ for(int j=1; j<n; j++){ if(str1[i-1] == str2[j-1]) { length[i][j] = length[i-1][j-1] + 1; state[i][j] = 0; }else if(length[i][j-1] >= length[i-1][j]) { length[i][j] = length[i][j-1]; state[i][j] = -1; //列数减一 }else { length[i][j] = length[i-1][j]; state[i][j] = 1; //行数减一 } } } //至此获得了最长子序列的长度，和子序列的匹配情况 //打印最长子序列 stack<char> lcs; for(int i=m-1, j=n-1; i>=0 && j>=0;){ if(state[i][j] == 0){//说明str1的第i个元素和str2的第j个元素相同 lcs.push(str1[i-1]); i--; j--; }else if(state[i][j] == 1){ i--; //行数减一 }else{ j--; //列数减一 } } if(lcs.empty()){ cout<<"没有公共子序列"<<endl; return ; } cout<<"最长的子序列："; while(!lcs.empty()){ cout<<lcs.top(); lcs.pop(); } cout<<"\n其长度为："<<length[m-1][n-1]; return ; } int main(){ string str1 = {"abcdefghijklmnree"}; string str2 = {"cdfgrrze"}; cout<<"序列1："<<str1<<endl; cout<<"序列2："<<str2<<endl; getLCS(str1,str2); return 0; }运行结果：（使用VS Code 编译运行）
初学动态规划，以上只是个人理解，表达的可能不够准确，还望各位大佬指点！！！
