Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #16761

Re: on distinguishing memoization and dynamic programming

Cross-posted to 3 groups.

Show all headers | View raw

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.

Back to comp.programming | Previous | Next — Previous in thread | Next 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
  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