educative.io

Why doesn't memoization of the simple recursion work?

Courses
,
#1

Why does memoizing the recursion for the matrix chain multiplication not work (for efficiency purposes)? (see below)

memo={}

def minMultiplications(dims):

if (len(dims)<=2): 

# write your code here

    return 0

elif tuple(dims) in memo:

    return memo[tuple(dims)]

else:

    cand=[]

    for i in range(3,len(dims)+1,1):

        dim1= dims[:i-2] + dims[i-1:]

        cand.append( dims[i-3] * dims[i-2]*dims[i-1] + minMultiplications(dim1)  )

    memo[tuple(dims)]=min(cand)

    return min(cand)

stressTesting = True

#2

Since the problem computes the same subproblems again and again, there is no reason why memoization should not work. If you look at the time complexities you can see that the memoized problem has O(n^3​​​) while the simple recursion has O(n^2 2^n).

lets take the case for n=100: the simple recursion=1.2676506e+34 and the memoized recursion=1000000.

So you can see a massive difference in time.

Hope this helps

#3

That’s why I’m asking because from a theoretical perspective memoization should work. When I run the code though it fails stress testing i.e. setting stresstesting=True makes it not work.