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

最长公共子序列问题可以用动态规划的方法求解。其中，自顶向下的方式可以使用递归加记忆化搜索的方式来实现。具体步骤如下：

1. 定义状态：设 $dp[i][j]$ 表示序列 $A$ 的前 $i$ 个元素和序列 $B$ 的前 $j$ 个元素的最长公共子序列的长度。

2. 确定状态转移方程：当 $A[i]=B[j]$ 时，$dp[i][j]=dp[i-1][j-1]+1$；当 $A[i]\neq B[j]$ 时，$dp[i][j]=\max(dp[i-1][j],dp[i][j-1])$。

3. 初始化：$dp[i][0]=0$，$dp[0][j]=0$。

4. 最优解：$dp[m][n]$，其中 $m$ 和 $n$ 分别是序列 $A$ 和 $B$ 的长度。

5. 最优值：$dp[m][n]$。

下面是 C 语言代码实现：

#include <stdio.h>
#include <string.h>

#define MAXN 100

int dp[MAXN][MAXN];
int vis[MAXN][MAXN];

int max(int a, int b)
{
    return a > b ? a : b;
}

int lcs(char A[], char B[], int i, int j)
{
    if (i == 0 || j == 0)
        return 0;
    if (vis[i][j])
        return dp[i][j];
    vis[i][j] = 1;
    if (A[i] == B[j])
        dp[i][j] = lcs(A, B, i - 1, j - 1) + 1;
    else
        dp[i][j] = max(lcs(A, B, i - 1, j), lcs(A, B, i, j - 1));
    return dp[i][j];
}

int main()
{
    char A[] = "ABCBDAB";
    char B[] = "BDCABA";
    int m = strlen(A);
    int n = strlen(B);
    printf("最长公共子序列的长度为：%d\n", lcs(A, B, m, n));
    return 0;
}

以上代码的输出结果为：

最长公共子序列的长度为：4

其中，序列 "BCBA" 是 $A$ 和 $B$ 的最长公共子序列。