Табулирование и памятка для решений по возврату в динамическом программировании c (например, LCS)

Question

Допустим, мы подходим к проблеме самой длинной общей подпоследовательности между двумя строками с помощью Dynami c Программирование с использованием либо Memoization (подход сверху вниз), либо Tabulation (снизу вверх).

Мой вопрос: какой из этих двух методов может быть изменен, чтобы дополнительно вернуть самую длинную общую строку (за пределами ее длины)? Что я имею в виду под этим:

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

, какой из этих двух методов может быть изменен, чтобы дополнительно вернуть самую длинную общую строку (сверх ее длины)

Оба могут быть,

Можно ли изменить оба метода для достижения этой цели ...

Да,

... или это зависит от проблемы?

Нет.

Если вы внедряете LCS самостоятельно, добавить это просто. Гораздо сложнее найти этого LCS. Что касается вопроса, лучше ли использовать памятку или табулирование, посмотрите на этот ответ { ссылка }