题目：
给定两个字符串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列置0
for (i = 1; i <= m; i++)c[i][0] = 0;
for (j = 1; j <= n; j++)c[0][j] = 0;
//根据递推公式构造数组c
for(i=1;j<=m;i++)
for (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])
{
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 <= 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 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);
}