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?
On 2024-01-03, Julieta Shem <jshem@yaxenu.org> 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.
Memoization helps when the recursion leads to overlapping subproblems
that lead to an exponential explosion if the duplication is not
identified and suppressed.
On 2024-01-03, Julieta Shem <jshem@yaxenu.org> 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?
Did you check Wikipedia?
https://en.wikipedia.org/wiki/Dynamic_programming
Dynamic programming is an "algorithmic paradigm" according to this page;
a nice term.
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.
On 2024-01-03, Julieta Shem <jshem@yaxenu.org> 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.
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?
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.
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.
Thanks for the analogy.
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 414 |
Nodes: | 16 (2 / 14) |
Uptime: | 67:56:02 |
Calls: | 8,677 |
Calls today: | 6 |
Files: | 13,247 |
Messages: | 5,944,381 |