从 Python 中的子序列中找到最大化回文长度的程序
假设我们有两个字符串，s 和 t。我们想以下列方式制作一个字符串 -
从 s 中选择一些非空子序列 sub1。
从 t 中选择一些非空子序列 sub2。
连接 sub1 和 sub2，以生成字符串。
我们必须找到可以以所描述的方式形成的最长回文的长度。如果我们不能生成任何回文，则返回 0。
因此，如果输入类似于 s = "hillrace" t = "cargame"，那么输出将是 7，因为我们可以从 s 中获取“race”，从 r 中获取“car”，所以“racecar”是长度为 7 的回文.
示例
让我们看下面的实现来更好地理解
def solve(s, t):n, m = len(s), len(t)
word = s + t
dp = [[0] * (n + m) for _ in range(n + m)]
for i in range(n + m - 1, -1,-1):
for j in range(i, n + m):
if i == j:
dp[i][j] = 1
elif word[i] == word[j]:
dp[i][j] = 2 + dp[i + 1][j - 1]
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
ans = 0
for i in range(n):
for j in range(m - 1, -1, -1):
if s[i] == t[j]:
ans = max(ans, dp[i][n + j])
return ans
s = "hillrace"
t = "cargame"
print(solve(s, t))
输入
[[2,2],[1,2],[3,2]], [[3,1],[3,3],[5,2]]输出结果
7
以上是 从 Python 中的子序列中找到最大化回文长度的程序 的全部内容， 来源链接： utcz.com/z/355710.html
