Path: ...!feeds.phibee-telecom.net!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: HenHanna <HenHanna@devnull.tb>
Newsgroups: comp.programming,comp.lang.lisp,sci.lang
Subject: Re: on distinguishing memoization and dynamic programming
Date: Tue, 23 Jul 2024 12:15:50 -0700
Organization: A noiseless patient Spider
Lines: 63
Message-ID: <v7ovh6$1b339$1@dont-email.me>
References: <87frzembwb.fsf@yaxenu.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 23 Jul 2024 21:15:51 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="45120b53e64fc89465e7bcc84dd55152";
	logging-data="1412201"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/7xRnl+BAbZ0wWcWtFqWp5FJ5mnLYIEUo="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:Dd70xKDSCeuMSpd7zJxT//pa9+0=
Content-Language: en-US
In-Reply-To: <87frzembwb.fsf@yaxenu.org>
Bytes: 2875


On 1/3/2024 11:53 AM, 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?



Memoization and dynamic programming are both techniques used to improve 
the efficiency of algorithms, but there are some key differences between 
them:

--------------Memoization:

Focus: Caching previously computed results
Approach: Top-down (usually implemented with recursion)
Applicability: Any function with repeated computations for the same inputs



Example: Imagine a function that calculates the nth Fibonacci number. 
Recursive calls to calculate smaller Fibonacci numbers happen 
repeatedly. Memoization remembers these calculations and avoids 
redundant computations.





--------Dynamic Programming:

Focus: Solving problems with overlapping subproblems iteratively

Approach: Bottom-up (often uses tables or arrays)

Applicability: Problems where solutions to subproblems contribute to the 
solution of larger problems


Example:        Counting the number of ways to climb stairs.
        You can find the number of ways to climb 1 or 2 stairs, and then 
use those to find the number of ways to climb 3 stairs, and so on.


The Relationship:

Memoization can be considered a tool used within dynamic programming.


Dynamic programming doesn't necessarily require memoization, it can 
solve problems bottom-up directly.



Here's an analogy:

Think of memoization as a to-do list app. You write down tasks you've 
already completed to avoid doing them again.

Dynamic programming is like a recipe.          You break down a complex 
dish into smaller steps, ensuring you only perform each step once.