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

发布网友发布时间：2022-05-05 00:56

共1个回答

热心网友时间：2023-10-03 06:41

最长公共子序列（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]
虽然是百度的，但是还是望采纳。

声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com