What is the difference between memoization and dynamic programming?

by

Relevant article on Programming.Guide: Dynamic programming vs memoization vs tabulation

What is difference between memoization and dynamic programming?

Memoization is a term describing an optimization technique where you cache previously computed results, and return the cached result when the same computation is needed again.

Dynamic programming is a technique for solving problems of recursive nature, iteratively and is applicable when the computations of the subproblems overlap.

Dynamic programming is typically implemented using tabulation, but can also be implemented using memoization. So as you can see, neither one is a “subset” of the other.

A reasonable follow-up question is: What is the difference between tabulation (the typical dynamic programming technique) and memoization?

When you solve a dynamic programming problem using tabulation you solve the problem “bottom up“, i.e., by solving all related sub-problems first, typically by filling up an n-dimensional table. Based on the results in the table, the solution to the “top” / original problem is then computed.

If you use memoization to solve the problem you do it by maintaining a map of already solved sub problems. You do it “top down” in the sense that you solve the “top” problem first (which typically recurses down to solve the sub-problems).

A good slide from here (link is now dead, slide is still good though):

  • If all subproblems must be solved at least once, a bottom-up dynamic-programming algorithm usually outperforms a top-down memoized algorithm by a constant factor
    • No overhead for recursion and less overhead for maintaining table
    • There are some problems for which the regular pattern of table accesses in the dynamic-programming algorithm can be exploited to reduce the time or space requirements even further
  • If some subproblems in the subproblem space need not be solved at all, the memoized solution has the advantage of solving only those subproblems that are definitely required

Additional resources:

More Related Contents:

  1. What is the difference between bottom-up and top-down?
  2. How to determine the longest increasing subsequence using dynamic programming?
  3. Is there a generic way to memoize in Scala?
  4. What’s the difference between a module and package in Python?
  5. Definition of “downstream” and “upstream”
  6. What exactly are iterator, iterable, and iteration?
  7. What are non-lexical lifetimes?
  8. What is a lambda (function)?
  9. What is the difference between an Abstract Syntax Tree and a Concrete Syntax Tree?
  10. count vs length vs size in a collection
  11. Is there a decorator to simply cache function return values?
  12. What is the meaning of “cascading’ in CSS?
  13. What are iterator, iterable, and iteration?
  14. What do < and > stand for?
  15. What’s the difference between a proxy server and a reverse proxy server? [closed]
  16. Static/Dynamic vs Strong/Weak
  17. What is a practical use for a closure in JavaScript?
  18. Framework vs. Toolkit vs. Library [duplicate]
  19. Writing Universal memoization function in C++11
  20. Difference between an application server and a servlet container?
  21. What type to use to store an in-memory mutable data table in Scala?
  22. Python – anyone have a memoizing decorator that can handle unhashable arguments?
  23. Options for caching / memoization / hashing in R
  24. What is a web service endpoint?
  25. Sliding window maximum in O(n) time
  26. Sort array using array_multisort() with dynamic number of arguments/parameters/rules/data
  27. What exactly are C++ definitions, declarations and assignments?
  28. What is the difference between the kernel space and the user space?
  29. Memoization of promise-based function
  30. What does “semantically correct” mean?

Leave a Comment