Re: on distinguishing memoization and dynamic programming

Path	csiph.com!news.mixmin.net!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
Date	Wed, 03 Jan 2024 20:19:07 -0300
Organization	A noiseless patient Spider
Lines	37
Message-ID	<87o7e2kntg.fsf@yaxenu.org> (permalink)
References	<87frzembwb.fsf@yaxenu.org> <20240103120043.381@kylheku.com> <87zfxmkugm.fsf@yaxenu.org> <20240103144433.679@kylheku.com>
MIME-Version	1.0
Content-Type	text/plain
Injection-Info	dont-email.me; posting-host="51130c85bb34424d24cba7c06e8521ff"; logging-data="3546571"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX185WfNtel+RchnE9njucI0ogfQ5BUZ3MyI="
Cancel-Lock	sha1:WrjRpZhiOWKQwfEB35L1vMl9z7E= sha1:hvk+m6pd2zmKcqscFmln7kTPJ6E=
Xref	csiph.com comp.lang.lisp:57004 comp.programming:16715

Cross-posted to 2 groups.

Show key headers only | View raw

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

> On 2024-01-03, Julieta Shem <jshem@yaxenu.org> wrote:
>> 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.
>
> The famous example is Fibonacci. If you calculate fib(7) recursively,
> fib(3), and others, will show up more than once in the recursion:
>
>               fib(7)
>              /      \
>        fib(6)        fib(5)
>        /    \       /      \
>    fib(4)   fib(5) fib(4)   fib(3)
>            /     \         /     \
>          fib(4) fib(3)
>         /     \ /    \
>
> Why is that called overlapping? Because the left subtree fib(6)
> and fib(5) are not the same, but they contain some common content
> (nodes that are exactly the same like another copy of fib(5), and
> multiple fib(4) and so on).
>
> It's just in contrast to divide-and-conquer, where the problem
> space is being strictly partitioned; no part or sub-part of the
> left tree occcurs in the right or vice versa.
>
> [0, 10] and [5, 15] overlap, and they have [5, 10] in common.
> If that can be solved as a sub-problem, such that we can solve
> [0, 4], [5, 10] and [11, 15], and put them together,
> that would be better than solving [5, 10] twice and doing
> the same thing.

That's very clear now.  Wonderful.  Thank you.

Back to comp.lang.lisp | Previous | Next — Previous 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

csiph-web