用于动态编程（ex LCS）中回溯解决方案的制表与记忆化]]

Question

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

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

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问题）。

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

Answer 1

这两种方法中的哪一种可以更改，以附加返回最长的通用字符串（超出其长度）