13问答网 > 问一道动态规划算法题. 设A和B是长度相等,长度为n的字符串. 他们的最长公共子串长度为(n-L)

问一道动态规划算法题. 设A和B是长度相等,长度为n的字符串. 他们的最长公共子串长度为(n-L)

2025-04-30 00:15:06

推荐回答（1个）

回答1：

最长公共子序列（Longest-Common-Subsequence，LCS）
dp[i][j]：dp[i][j]表示长度分别为i和j的序列X和序列Y构成的LCS的长度
dp[i][j] = 0，如果i=0 或 j=0
dp[i][j] = dp[i-1][j-1] + 1，如果 X[i-1] = Y[i-1]
dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }，如果 X[i-1] != Y[i-1]
LCS长度为 dp[Xlen][Ylen]