Groups | Search | Server Info | Login | Register

Groups > comp.programming > #16713

Re: on distinguishing memoization and dynamic programming

Cross-posted to 2 groups.

Followups directed to: comp.programming

Show all headers | 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