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

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.