CODEWITHSUNDEEP
dynamic-programmingmemoization
matsko
matsko

Reputation: 22193

Implementation of memoization vs dynamic programming lookups

Before I get started, no this isn't a question asking what the different between memoization and dynamic programming nor which one is better, but just a simple question asking about a minor difference between the way that they handle cached lookups.

DP uses a bottom-up approach while memoization uses a top-down. So with DP you start out by building a table of cached calculations and then feeding those cached values to bigger calculations to avoid redundant recursive or iterative function calls. Memoization is more or less just caching each function call's result into a hash or an array (probably an array) and then providing the result within the function call (it just skips anything that happens within the body of the function).

My question is that I am correct with what I am stating here? Both approaches look similar only DP is harder and slightly more efficient with memory compared to memoization. With memoization your program still has to fire off each function call even if it is cached and each and every one of these function calls can quickly feed up the stack, whereas in DP it would check the array table within the function and only calling the recursive/iterative function if its not found.

Am I correct here? Or am I missing something?

Upvotes: 1

Views: 523

Answers (2)

Amir Afghani
Amir Afghani

Reputation: 38531

Dynamic programming and memo-ization are not mutually exclusive, or different approaches. Memo-ization is just 'remembering' the result of a function call with all of its relevant context(parameters, invoking instance, etc). Dynamic programming uses memo-ization to achieve the goal of computing the result of a given sub problem only once.

From Wikipedia:

The dynamic programming approach seeks to solve each subproblem only once, thus reducing the number of computations: once the solution to a given subproblem has been computed, it is stored or "memo-ized": the next time the same solution is needed, it is simply looked up. This approach is especially useful when the number of repeating subproblems grows exponentially as a function of the size of the input.

Upvotes: 2

Charlie Martin
Charlie Martin

Reputation: 112366

Well, I think you're basically making too restrictive a definition of "memoization", which is really just any technique of storing previously computed results rather than recomputing them. So a Fibonacci calculation that stores all the results up to a previous high n is memoizing, but so is a DP algorithm that stores previously computed subproblems.

(See the Wikipedia article.)

Upvotes: 2

Related Questions