Groups | Search | Server Info | Login | Register

Groups > comp.lang.lisp > #57004

Re: on distinguishing memoization and dynamic programming

Cross-posted to 2 groups.

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