Tabulation vs Memoization for Backtracking solutions in Dynamic Programming (ex LCS)

2
votes

Let’s say we approach the Longest Common Subsequence problem between two strings with Dynamic Programming using either Memoization (Top Down approach) or Tabulation (Bottom Up).

My question is, which of these two methods can be altered in order to additionally return the longest common string (beyond its length) ? What I mean by that:

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])

Do both methods are able to be altered to achieve this or does it depend on the problem ?

[EDIT]
My intuition is that memoization approach can be “easily” altered in order to also keep track of the actual solution. But, I don’t see an easy way (or a general way) to backtrack the solution given the “table contents” in the tabulation approach. Please answer as general as possible (not specifically for the LCS problem).

1
dynamic-programmingbacktrackingmemoizationtopdownbottom-up
It's your choice to put a bounty on this, but I don't see why. There's nothing new in this question. Reviewing the well-known LCS algorithms will answer your question fully (including the more general case). – Elliott

1 Answers

1
votes

which of these two methods can be altered in order to additionally return the longest common string (beyond its length)

Both can be,

Do both methods are able to be altered to achieve this...

Yes,

...or does it depend on the problem ?

No.

If you are implementing the LCS on your own, then it's trivial to have that added. It's much harder to find that LCS in the first place. As for the question whether it is better to use memoization or tabulation, please look at this answer https://stackoverflow.com/a/6185005/11729048