XPost: comp.lang.lisp   
   From: jshem@yaxenu.org   
      
   Kaz Kylheku <433-929-6894@kylheku.com> writes:   
      
   > On 2024-01-03, Julieta Shem  wrote:   
   >> I was trying to distinguish memoization from dynamic programming --- in   
   >> a technical way --- and I failed.  Can you write something like a   
   >> mathematical definition of each one?   
      
   [...]   
      
   > Dynamic programming breaks a larger problem into sub-problems which   
   > can be solved separately and then integrated to solve the   
   > larger problem.   
      
   I can't distinguish this definition from ``recursive''.   
      
   > Memoization helps when the recursion leads to overlapping subproblems   
   > that lead to an exponential explosion if the duplication is not   
   > identified and suppressed.   
      
   So it seems to be that memoization is a particular kind of strategy that   
   falls in the dynamic programming set of strategies.  (Thanks for the   
   historical addendum in your other post.)   
      
   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.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)