What are some pros and cons of Tabulation or Bottom-Up approach?

Technology CommunityCategory: Dynamic ProgrammingWhat are some pros and cons of Tabulation or Bottom-Up approach?
VietMX Staff asked 3 years ago

Pros:

  • If you are doing an extremely complicated problems, you might have no choice but to do tabulation (or at least take a more active role in steering the memoization where you want it to go). Also if you are in a situation where optimization is absolutely critical and you must optimize, tabulation will allow you to do optimizations which memoization would not otherwise let you do in a sane way.
    • Why? Because with memoization, if the tree is very deep (e.g. fib(10^6)), you will run out of stack space, because each delayed computation must be put on the stack, and you will have 10^6 of them.
  • In many applications the bottom-up approach is slightly faster because of the overhead of recursive calls.

Cons:

  • The downside of tabulation is that you have to come up with an ordering. You must pick, ahead of time, the exact order in which you will do your computations.
  • Top-down only solves sub-problems used by your solution whereas bottom-up might waste time on redundant sub-problems.