Groups | Search | Server Info | Login | Register
Groups > comp.programming > #16711
| From | Kaz Kylheku <433-929-6894@kylheku.com> |
|---|---|
| Newsgroups | comp.lang.lisp, comp.programming |
| Subject | Re: on distinguishing memoization and dynamic programming |
| Date | 2024-01-03 20:06 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <20240103120043.381@kylheku.com> (permalink) |
| References | <87frzembwb.fsf@yaxenu.org> |
Cross-posted to 2 groups.
On 2024-01-03, Julieta Shem <jshem@yaxenu.org> wrote: > I was trying to distinguish memoization from dynamic programming --- in > a technical way --- and I failed. Can you write something like a > mathematical definition of each one? Did you check Wikipedia? https://en.wikipedia.org/wiki/Dynamic_programming Dynamic programming is an "algorithmic paradigm" according to this page; a nice term. Memoization is a specific algorithmic trick, which is used in some solutions that fall into the dynamic programming paradigm. (It is used essentially, so that practically useful run-times can be achieved: e.g. exponential time knocked down to polynomial.) Dynamic programming breaks a larger problem into sub-problems which can be solved separately and then integrated to solve the larger problem. Memoization helps when the recursion leads to overlapping subproblems that lead to an exponential explosion if the duplication is not identified and suppressed. -- TXR Programming Language: http://nongnu.org/txr Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal Mastodon: @Kazinator@mstdn.ca NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.
Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar
on distinguishing memoization and dynamic programming Julieta Shem <jshem@yaxenu.org> - 2024-01-03 16:53 -0300
Re: on distinguishing memoization and dynamic programming Kaz Kylheku <433-929-6894@kylheku.com> - 2024-01-03 20:06 +0000
Re: on distinguishing memoization and dynamic programming Kaz Kylheku <433-929-6894@kylheku.com> - 2024-01-03 20:16 +0000
Re: on distinguishing memoization and dynamic programming Julieta Shem <jshem@yaxenu.org> - 2024-01-03 17:55 -0300
Re: on distinguishing memoization and dynamic programming Kaz Kylheku <433-929-6894@kylheku.com> - 2024-01-03 22:58 +0000
Re: on distinguishing memoization and dynamic programming Julieta Shem <jshem@yaxenu.org> - 2024-01-03 20:19 -0300
Re: on distinguishing memoization and dynamic programming Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-01-12 16:41 -0800
Re: on distinguishing memoization and dynamic programming HenHanna <HenHanna@devnull.tb> - 2024-07-23 12:15 -0700
Re: on distinguishing memoization and dynamic programming Julieta Shem <jshem@yaxenu.org> - 2024-07-23 21:06 -0300
Re: on distinguishing memoization and dynamic programming HenHanna <HenHanna@devnull.tb> - 2024-07-24 01:04 -0700
csiph-web