蓝桥杯每日一练——最长公共子序列问题（动态规划）

题目：
给定两个字符串txet1和text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列 ，返回 0 。 

示例1输入：text1 = "abcde", text2 = "ace" 输出：3  解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例2输入：text1 = "abc", text2 = "abc"输出：3解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例3输入：text1 = "abc", text2 = "def"输出：0解释：两个字符串没有公共子序列，返回 0 。

最长公共子序列https://leetcode-cn.com/problems/qJnOS7/

最长公共子序列问题：

若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。

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

给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

最长公共子序列是dp（动态规划）经典例题，求解方法也十分经典，通过分析最有子结构构造二维数组 

构造二维数组c 

问题一：求出公共子序列长度 

void LCSlength(int m, int n, const char x[], char y[]){int i, j;//数组c的第0行第0列置0for (i = 1; i <= m; i++)c[i][0] = 0;for (j = 1; j <= n; j++)c[0][j] = 0;//根据递推公式构造数组cfor(i=1;j<=m;i++)for (j = 1; j =c[i][j]){c[i][j] = c[i - 1][j];}else{c[i][j] = c[i][j - 1];}}}

 问题二：求出公共子序列

 分析：问题二通常要设辅助数组b来记录c[i][j]的数值是如何填写的

这是c[i][j]来自的方向 

void LCSLength　(int m, int n, const char x[],char y[]){  　　int i,j;　　//数组c的第0行、第0列置0　　for (i = 1; i <= m; i++) c[i][0] = 0;　　for (i = 1; i <= n; i++) c[0][i] = 0;　　//根据递推公式构造数组c　　for (i = 1; i <= m; i++)　　for (j = 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 i, int j, char x[]){if (i == 0 || j == 0) return;if (b[i][j] == 1) { LCS(i - 1, j - 1, x);　 printf("%c", x[i]); }else if (b[i][j] == 2) LCS(i - 1, j, x);else LCS(i, j - 1, x);}