Path: csiph.com!pasdenom.info!news.gegeweb.eu!gegeweb.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Julieta Shem Newsgroups: comp.lang.lisp,comp.programming Subject: Re: on distinguishing memoization and dynamic programming Followup-To: comp.programming Date: Wed, 03 Jan 2024 17:55:37 -0300 Organization: A noiseless patient Spider Lines: 28 Message-ID: <87zfxmkugm.fsf@yaxenu.org> References: <87frzembwb.fsf@yaxenu.org> <20240103120043.381@kylheku.com> MIME-Version: 1.0 Content-Type: text/plain Injection-Info: dont-email.me; posting-host="75a951e1f41ca440471c166e12474bef"; logging-data="3510207"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19a8hzPV8xdUiv57iu9jDKT0rU/TxYW76A=" Cancel-Lock: sha1:6dxkR2R+0wxWiXKD9IdZktqDuQI= sha1:/kbSULkf0ftX7XVIBZKA05uNoQY= Xref: csiph.com comp.lang.lisp:57000 comp.programming:16713 Kaz Kylheku <433-929-6894@kylheku.com> writes: > On 2024-01-03, Julieta Shem 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? [...] > Dynamic programming breaks a larger problem into sub-problems which > can be solved separately and then integrated to solve the > larger problem. I can't distinguish this definition from ``recursive''. > Memoization helps when the recursion leads to overlapping subproblems > that lead to an exponential explosion if the duplication is not > identified and suppressed. So it seems to be that memoization is a particular kind of strategy that falls in the dynamic programming set of strategies. (Thanks for the historical addendum in your other post.) Why do they say ``overlapping subproblems'' when it seems that what is meant is a duplicate problem? For instance, the interval [0, 10] overlaps with the interval [5, 15], but they're not the same. AFAICT, memoization is only useful when at least two of the subproblems are exactly the same.