Sorry for the spam guys, I have one more question if anyone is up for taking it. Here goes:
To start with, I think I understand the 3 approaches (naive, memoization, tabulation). My question however is this: Does the memoization and tabulation methods use the bool array to represent two entirely different things?
Reason for my asking is:
- tabulation is generally considered as the next step after memoization, where we remove the recursion and fill the table intentionally by iteration.
- so, if they were to represent the same things, the table filled by either method should have identical values, although the order in which they are filled would be different. Am I correct here?
For an example string
catdog and a dictionary
Tabulation's table looks like
[true, false, false, true, false, false, true].
(What it means?
true => end pos of string
false => end position of other splits that do not form valid words)
Memoization's cache looks like
[true, null, null, true, null, null].
(What it means? I'm not sure. I guess I don't exactly understand what computation is repeated, for that's what is being cached here. May be i picked a bad example that doesn't show whats repeated but despite that I'm not clear on the repeated computation that we're optimizing).