What are pros and cons of Memoization or Top-Down approach?

Technology CommunityCategory: Dynamic ProgrammingWhat are pros and cons of Memoization or Top-Down approach?
VietMX Staff asked 3 years ago

Pros:

  • Memoization is very easy to code (you can generally* write a “memoizer” annotation or wrapper function that automatically does it for you), and should be your first line of approach. It feels more natural. You can take a recursive function and memoize it by a mechanical process (first lookup answer in cache and return it if possible, otherwise compute it recursively and then before returning, you save the calculation in the cache for future use), whereas doing bottom up dynamic programming requires you to encode an order in which solutions are calculated.
  • Top-down only solves sub-problems used by your solution whereas bottom-up might waste time on redundant sub-problems.

Cons:

  • With memoization, if the tree is very deep (e.g. fib(106)), you will run out of stack space, because each delayed computation must be put on the stack, and you will have 106 of them.