XPost: comp.lang.lisp   
   From: jshem@yaxenu.org   
      
   Kaz Kylheku <433-929-6894@kylheku.com> writes:   
      
   > On 2024-01-03, Julieta Shem  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.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)