C语言求解最长公共子序列问题，给出最优值和最优解，并且通过实例验证：用自底向上方式求解

最长公共子序列问题是指给定两个序列，找到它们之间最长的公共子序列。可以使用动态规划来解决该问题。

具体来说，设两个序列分别为 $A=a_1,a_2,\cdots,a_m$ 和 $B=b_1,b_2,\cdots,b_n$，定义 $L(i,j)$ 为 $A$ 的前 $i$ 个元素和 $B$ 的前 $j$ 个元素的最长公共子序列长度，则可以得到以下递推式：

$$
L(i,j)=\begin{cases}
0 & i=0 \text{ 或 } j=0 \\
L(i-1,j-1)+1 & a_i=b_j \\
\max(L(i-1,j),L(i,j-1)) & a_i\neq b_j
\end{cases}
$$

其中第一行是边界条件，即空序列的最长公共子序列长度为 $0$；第二行表示当 $a_i=b_j$ 时，可以将当前元素加入前面的最长公共子序列中；第三行表示当 $a_i\neq b_j$ 时，当前元素不能同时出现在两个序列的最长公共子序列中，因此需要在 $A$ 的前 $i-1$ 个元素和 $B$ 的前 $j$ 个元素中找到最长公共子序列，或者在 $A$ 的前 $i$ 个元素和 $B$ 的前 $j-1$ 个元素中找到最长公共子序列，取较大值即可。

根据上述递推式，可以使用自底向上的方式进行求解。具体来说，可以使用一个二维数组 $dp$ 存储 $L(i,j)$ 的值，$dp[i][j]$ 表示 $A$ 的前 $i$ 个元素和 $B$ 的前 $j$ 个元素的最长公共子序列长度。初始化 $dp$ 数组为 $0$，然后按照递推式计算 $dp$ 数组中的每一个元素，最终 $dp[m][n]$ 就是 $A$ 和 $B$ 的最长公共子序列长度。

同时，可以根据 $dp$ 数组还原出最长公共子序列。具体来说，可以从 $dp[m][n]$ 开始，向左上方遍历 $dp$ 数组，每次遇到 $dp[i][j]=dp[i-1][j-1]+1$ 时，将 $a_i$ 加入最长公共子序列中，直到 $i=0$ 或 $j=0$。

下面给出一个示例：

假设 $A=1,3,2,4,5,7,6$，$B=2,4,3,6,5,8,7$，求它们的最长公共子序列。

首先，初始化 $dp$ 数组为：

$$
\begin{matrix}
& & & & & & & \\
& 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
& 0 & & & & & & \\
& 0 & & & & & & \\
& 0 & & & & & & \\
& 0 & & & & & & \\
& 0 & & & & & & \\
& 0 & & & & & & \\
\end{matrix}
$$

然后按照递推式计算 $dp$ 数组中的每一个元素，得到：

$$
\begin{matrix}
& & & & & & & \\
& 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
& 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
& 0 & 1 & 1 & 1 & 2 & 2 & 2 \\
& 0 & 1 & 1 & 2 & 2 & 2 & 2 \\
& 0 & 1 & 2 & 2 & 3 & 3 & 3 \\
& 0 & 1 & 2 & 2 & 3 & 3 & 4 \\
& 0 & 1 & 2 & 2 & 3 & 4 & 4 \\
\end{matrix}
$$

可以发现，$dp[7][6]=4$，即 $A$ 和 $B$ 的最长公共子序列长度为 $4$。

最后，根据 $dp$ 数组还原出最长公共子序列。从 $dp[7][6]$ 开始，向左上方遍历 $dp$ 数组，每次遇到 $dp[i][j]=dp[i-1][j-1]+1$ 时，将 $a_i$ 加入最长公共子序列中，直到 $i=0$ 或 $j=0$。具体来说，可以得到最长公共子序列为 $3,4,5,7$。

因此，$A$ 和 $B$ 的最长公共子序列长度为 $4$，最长公共子序列为 $3,4,5,7$。