假设我们使用记忆(自上而下方法(或制表(自下而上(通过动态规划处理两个字符串之间的最长公共子序列问题。
我的问题是,这两种方法中的哪一种可以更改以额外返回最长的公共字符串(超出其长度(? 我的意思是:
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问题(。
方法中的哪一种可以更改以另外 返回最长的公共字符串(超出其长度(
两者都可以是,
这两种方法都可以改变以实现这一点吗?
是的
。还是取决于问题?
不。
如果您自己实现 LCS,那么添加它就很简单了。首先要找到LCS要困难得多。至于用记忆还是制表好的问题,请看这个答案 https://stackoverflow.com/a/6185005/11729048