Memoization Memory

Question

Memoization is definitely a powerful technique.

But Dynamic Programming is slightly better IMO, since it does not involve the memory strain (in a recursive program, the parameters occupy memory and this memory increases as we go deeper into the recursion). But speed-wise, both are pretty equal.

But definitely memoization is a lot more straight-forward than Dynamic Programming.

My question: Is it somehow possible to use memoization without the memory constraint ?

• ratchet freak: you can combine dynamic programming and memoization
• user121210: @ratchet freak: How ? What is the use ?
• amon: DP is basically equivalent to memoization. The difference is that in DP, you generate the cache in a specific way and are aware of what cache entries are used when (compare a memoized factorial with O(n) memory, and the DP factorial with O(1) memory). Effectively, recursion (with memoization) is a top-down strategy, whereas DP constructs a solution bottom-up: the same, but from different directions.
• Brian: To expand upon amon's response, see SO: Dynamic programming and memoization: bottom-up vs top-down approaches for a more in depth explanation of the difference between Memoization and DP.

Answer 1

You can reduce the amount of memory used for memoization by using a "Least Recently Used" cache (with limited maximum size) for the memoized values. How well this works depends heavily on the problem, the function you are going to memoize and the choice of the cache size. But I guess for a problem where DP works well, there is a good chance that function values needed in a first stage of a calculation won't be needed any more some stages later, so the LRU strategy will free the resources for these values automatically.