What is the difference between memoization and dynamic programming?

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:

Related Posts:

  1. What is the difference between application server and web server?
  2. What is meant by diameter of a network?
  3. What is runtime in context of Python? What does it consist of?
  4. What is dependency injection?
  5. When is K 1024 and when is it 1000?
  6. Dial pad to get phone number (with Android button images)
  7. Why is it not possible to fake an IP address?
  8. Authentication versus Authorization
  9. What is tail recursion?
  10. What is a loop invariant?
  11. Visual List of iOS Fonts?
  12. How to get rid of the “No bootable medium found!” error in Virtual Box? [closed]
  13. “Parameter” vs “Argument”
  14. What does it mean if a Python object is “subscriptable” or not?
  15. What is Bit Masking?
  16. what is svn? and how to use it with project?
  17. How can I write a `try`/`except` block that catches all exceptions?
  18. How do I decompile a .dll file?
  19. What’s the purpose of git-mv?
  20. How to write trycatch in R
  21. how to use proxy on youtube-dl?
  22. SSH -X “Warning: untrusted X11 forwarding setup failed: xauth key data not generated”
  23. LINQ equivalent of foreach for IEnumerable
  24. How to do vlookup and fill down (like in Excel) in R?
  25. Using “super” in C++
  26. Were jprobes removed from kernel v4?
  27. ldap_sasl_bind(SIMPLE): Can’t contact LDAP server(-1)
  28. How to use vmImage on pipeline using Azure DevOps Server?
  29. git add . -> still “nothing to commit” with new files
  30. What is spaghetti code?
  31. git submodule add error: does not have a commit checked out
  32. “The certificate chain was issued by an authority that is not trusted” when connecting DB in VM Role from Azure website
  33. What’s the complete range for Chinese characters in Unicode?
  34. Is there an operation for not less than or not greater than in python?
  35. Resource interpreted as stylesheet but transferred with MIME type text/html (seems not related with web server)
  36. Background color for Tk in Python
  37. how to uninstall MinGW and make cygwin ‘make’ as deafult make program with gcc 3.8.1
  38. Cosine similarity and tf-idf
  39. Optional Parameters in Go?
  40. PostgreSQL: Remotely connecting to Postgres instance using psql command
  41. Android – Package Name convention
  42. How to execute an oracle stored procedure?
  43. How do I time a method’s execution in Java?
  44. -bash: export: `=’: not a valid identifier
  45. Error “The goal you specified requires a project to execute but there is no POM in this directory” after executing maven command
  46. Error in glm() in R
  47. What is a good Hash Function?
  48. Excel Filters – show only relevant values in the filter
  49. Unable to convert 3d ply file image to 2d image
  50. Get a random item from a JavaScript array
  51. Plotting horizontal and vertical lines in Mathematica
  52. Error while waiting for device: Time out after 300seconds waiting for emulator to come online
  53. How to transparent Unity3D custom shader?
  54. Converting string to integer VB.NET
  55. What is a loop invariant?
  56. Remove node_modules from git in vscode
  57. How do you change session timeout in IIS 8.5?
  58. Is it valid to have a html form inside another html form?
  59. what is shortcut command to kill process in windows command?
  60. Differentiate between function overloading and function overriding
  61. How to print variable in sml?
  62. Why is the minidlna database not being refreshed?
  63. java.sql.SQLException: Fail to convert to internal representation
  64. Representing EOF in C code?
  65. How to disable an Android button?
  66. How to set initial value and auto increment in MySQL?
  67. Chrome Broweser: csi.gstatic.com keeps loading
  68. How do you convert an entire directory with ffmpeg?
  69. What’s the difference between sx and σx in the statistics calculations on a TI-Nspire?
  70. Apache Kafka vs Apache Storm
  71. How can an Admin access the Google Drive contents of all the users in a particular domain?
  72. PSEXEC, access denied errors
  73. How do you define a global function in C++?
  74. A _disk_id.pod file appears on a windows flash drive
  75. What standard do language codes of the form “zh-Hans” belong to?
  76. What is the proof of of (N–1) + (N–2) + (N–3) + … + 1= N*(N–1)/2 
  77. Merge posts plugin? [closed]
  78. database collation differences
  79. Add Woocommerce product to cart with Contact Form 7 [closed]
  80. How to See Everything in get_option()?
  81. How can I prevent the WordPress Importer from munging double-newline paragraph breaks to a single newline?
  82. Slow WP Site, theme.php not caching? Up to 25 second load time! [closed]
  83. A Compare And Distinction Essay Define To Beat Writer’s Block
  84. 27 Outstanding Faculty Essay Examples
  85. The Way To Write An Essay Outline In Four Steps
  86. How to hide subfolder of static pages in WordPress using htaccess
  87. Javascript: Add anchor hashtag to URL, and reload
  88. To remove rendering of menus and header, plugin or theme?
  89. How to Unban an IP properly with Fail2Ban
  90. How to see stdout of ansible commands?
  91. Difference between KVM and QEMU
  92. How do I get the history of “apt-get install” on Ubuntu?
  93. Why does x86 represent 32bit when x64 represents 64bit? [closed]
  94. How to reload screenrc without restarting screen?
  95. How long before an s3 bucket can be created with same name after deletion?
  96. Software vs hardware RAID performance and cache usage
  97. How do high traffic sites service more than 65535 TCP connections?
  98. Using variables in Apache config files to reduce duplication?
  99. How to unify package installation tasks in ansible?
  100. Private IP address in public DNS

Leave a Comment

tech