算法 - 最长公共子序列记忆
我正在尝试解决最长公共子序列的著名问题 - 给定 2 个字符串，返回最长的子序列。具体来说，我的目标是返回实际序列，而不是序列的长度。例如，输入“ABCD”、“BD”将输出“BD”。下面是我写的代码，我不确定我使用的“memo”哈希表有什么问题。猜测密钥不够具体，但不确定原因。如何使用递归和备忘录数组/哈希表解决这个问题？我知道它可以用自下而上的动态规划算法来解决，但想用自上而下的方法进行更多练习。谢谢你！
def longestCommonSubsequence(str1, str2):
memo = {}
def recurse(i, j, sub):
key = (i, j)
if i == len(str1) or j == len(str2):
return sub
if str1[i] == str2[j]:
res = recurse(i + 1, j + 1, sub + [str1[i]])
memo[key] = res
return res
if key in memo:
return memo[key]
first = recurse(i + 1, j, sub)
second = recurse(i, j + 1, sub)
res = first if len(first) > len(second) else second
memo[key] = res
return res
return recurse(0, 0, [])
I am trying to solve a famous problem of longest common subsequence - given 2 strings, return the longest subsequence. To specify, my goal is to return the actual sequence, not the length of the sequence. For example, inputs "ABCD", "BD" would output "BD". Below is the code I wrote, and I'm not sure what is wrong with the "memo" hash table I'm using. Guessing the key is not specific enough but not sure why. How could I solve this problem using recursion and a memo array/ hash table? I know it is solvable with a bottom-up dynamic programming algorithm, but would like to practice more with top-down approach. Thank you!
def longestCommonSubsequence(str1, str2):
memo = {}
def recurse(i, j, sub):
key = (i, j)
if i == len(str1) or j == len(str2):
return sub
if str1[i] == str2[j]:
res = recurse(i + 1, j + 1, sub + [str1[i]])
memo[key] = res
return res
if key in memo:
return memo[key]
first = recurse(i + 1, j, sub)
second = recurse(i, j + 1, sub)
res = first if len(first) > len(second) else second
memo[key] = res
return res
return recurse(0, 0, [])
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论