CODEWITHSUNDEEP
pythonmemoization
rexorsist
rexorsist

Reputation: 107

How do you know when memoization should be used?

I'm learning about memoization and although I have no trouble implementing it when it's needed in Python, I still don't know how to identify situations where it will be needed.

I know it's implemented when there are overlapping subcalls, but how do you identify if this is the case? Some recursive functions seem to go deep before an overlapping call is made. How would you identify this in a coding interview? Would you draw out all the calls (even if some of them go 5-6 levels deep in an O(2^n) complexity brute force solution)?

Cases like the Fibonacci sequence make sense because the overlap happens immediately (the 'fib(i-1)' call will almost immediately overlap with the 'fib(i-2)' call). But for other cases, like the knapsack problem, I still can't wrap my head around how anyone can identify that memoization should be used while at an interview. Is there a quick way to check for an overlap?

I hope my question makes sense. If someone could point me to a good resource, or give me clues to look for, I would really appreciate it. Thanks in advance.

Upvotes: 0

Views: 97

Answers (1)

aamir
aamir

Reputation: 76

In order to reach the "memoization" solution, you first need to identify the following two properties in the problem:

  1. Overlapping subproblems
  2. Optimal substructure

Looks like you do understand (1). For (2):

Optimal Substructure: If the optimal solution to a problem, S, of size n can be calculated by JUST looking at optimal solution of a subproblem, s, with size < n and NOT ALL solutions to a subproblem, AND it will also result in an optimal solution for problem S, then this problem S is considered to have optimal substructure.

For more detail, please take a look at the following answer:

https://stackoverflow.com/a/59461413/12346373

Upvotes: 1

Related Questions