最长的公共子串(用直觉表示最长的公共子序列)

Question

我一直在努力学习动态编程。我遇到了两个看似相似的问题“最长的公共子序列”和“最长的公共子串”

所以我们假设我们有两个字符串str1和str2。

• For 最长公共子序列，我们以如下方式创建dp表：

if str1[i] != str2[j]:
    dp[i][j] = max(dp[i-1][j], sp[i][j-1])
else:
    dp[i][j] = 1 + dp[i-1][j-1]

遵循同样的直觉，对于“最长的公共子字符串”，我们可以执行以下操作：

if str1[i] != str2[j]:
    dp[i][j] = max(dp[i-1][j], sp[i][j-1])
else:
    if str1[i-1] == str2[j-1]:
        dp[i][j] = 1 + dp[i-1][j-1]
    else:
        dp[i][j] = 1 + dp[i-1][j-1]

检查if str1[i-1] == str2[j-1] 确认我们正在检查子字符串，而不是子序列。

Answer 1

我不明白您在问什么，但是我将尝试给最长的Common一个很好的解释。

设DPx是最大公共子字符串，考虑STR10.x和str20.y。

考虑到我们正在计算DPa，我们总是有可能不使用这个字符= max( DPa，DPa -1)，如果str1a == str2b，我们也可以接受DPa -1 +1的答案(因为我们找到了一个新的匹配字符)。

// This does not depend on s[i] == s[j]
dp[i][j] = max( dp[i][j - 1], dp[i - 1][j] )

if str1[i] == str2[j]:
    dp[i][j] = max( dp[i][j], dp[i - 1][j - 1] + 1 )