CODEWITHSUNDEEP
algorithmdynamic-programmingmemoization
user1151738
user1151738

Reputation:

Memoization Memory

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 ?

Upvotes: 0

Views: 219

Answers (1)

Sneftel
Sneftel

Reputation: 41474

You can think of DP as a form of memoization which benefits from extremely stringent guarantees on what access patterns occur. Memoization is a "pull" model, where the final answer requests its subparts and those requests lead (indirectly) to the smallest granularity of computation being invoked. DP is a "push" model, where the data that each computation will need is anticipated.

It's possible to reformulate any DP algorithm to use lazy computation and memoization instead of a table, and sometimes even to have the resultant implementation match DP in time and space complexity. however, the second trick generally comes down to keeping the DP implementation in mind and forcing the memoization implementation to "stumble upon" the same access patterns. It's a party trick, not a useful transformation.

Upvotes: 1

Related Questions