Groups | Search | Server Info | Keyboard shortcuts | Login | Register
Groups > comp.programming > #16714
| From | Kaz Kylheku <433-929-6894@kylheku.com> |
|---|---|
| Newsgroups | comp.lang.lisp, comp.programming |
| Subject | Re: on distinguishing memoization and dynamic programming |
| Date | 2024-01-03 22:58 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <20240103144433.679@kylheku.com> (permalink) |
| References | <87frzembwb.fsf@yaxenu.org> <20240103120043.381@kylheku.com> <87zfxmkugm.fsf@yaxenu.org> |
Cross-posted to 2 groups.
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.
--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.
Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar
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