2

假设我们使用记忆化（自上而下方法）或制表法（自下而上）使用动态编程来处理两个字符串之间的最长公共子序列问题。

我的问题是，可以更改这两种方法中的哪一种以另外返回最长的公共字符串（超出其长度）？我的意思是：

str1 = ‘abcdefg’
str2 = ‘@bcd@f@@‘

x = LCS(str1, str2)
y = LCS_altered(str1, str2)

# x = 4
# y = (4, ‘bcdf’) or (4, [False, True, True, True, False, True, False, False])

两种方法都可以改变来实现这一点还是取决于问题？

[编辑]
我的直觉是，记忆方法可以“轻松”更改，以便跟踪实际解决方案。但是，鉴于制表方法中的“表格内容”，我看不到一种简单的方法（或一般方法）来回溯解决方案。请尽可能笼统地回答（不是专门针对 LCS 问题）。

4

1 回答 1

1

可以更改这两种方法中的哪一种以另外返回最长的公共字符串（超出其长度）

两者都可以，

是否可以更改这两种方法以实现此目的...

是的，

...还是取决于问题？

不。

如果您自己实施 LCS，那么添加它是微不足道的。首先要找到LCS要困难得多。至于使用memoization还是tabulation更好的问题，请看这个答案https://stackoverflow.com/a/6185005/11729048

于 2020-02-22T13:06:51.307 回答