Groups | Search | Server Info | Login | Register

Re: on distinguishing memoization and dynamic programming

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 <jshem@yaxenu.org>
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> (permalink)
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

Cross-posted to 2 groups.

Followups directed to: comp.programming

Show key headers only | View raw

Kaz Kylheku <433-929-6894@kylheku.com> writes:

> 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?

[...]

> 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.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

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