最长公共子序列动态规划怎么填表

最长公共子序列问题可以使用动态规划算法来解决，其中填表是动态规划算法的核心步骤。下面是最长公共子序列动态规划填表的步骤：

1. 首先确定状态转移方程：设字符串X和Y的长度分别为m和n，令c[i][j]表示X的前i个字符和Y的前j个字符的最长公共子序列的长度。则当X[i]=Y[j]时，c[i][j] = c[i-1][j-1]+1；否则，c[i][j] = max(c[i-1][j], c[i][j-1])。

2. 创建一个二维数组c[m+1][n+1]，并将第一行和第一列初始化为0。

3. 从c[1][1]开始，按照状态转移方程依次填充c数组。填表的过程中，需要注意的是，对于每个c[i][j]，其值只和左边、上面和左上角三个位置的值有关。

4. 最终，c[m][n]即为字符串X和Y的最长公共子序列的长度。如果需要得到最长公共子序列的内容，可以倒推回去，具体方法可以参考其他资料。

下面是一个示例代码，演示了最长公共子序列动态规划填表的过程：

int lcs(string X, string Y) {
    int m = X.size();
    int n = Y.size();
    int c[m+1][n+1];
    for (int i = 0; i <= m; i++) {
        c[i][0] = 0;
    }
    for (int j = 0; j <= n; j++) {
        c[0][j] = 0;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i-1] == Y[j-1]) {
                c[i][j] = c[i-1][j-1] + 1;
            } else {
                c[i][j] = max(c[i-1][j], c[i][j-1]);
            }
        }
    }
    return c[m][n];
}