Re: on distinguishing memoization and dynamic programming

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.