Rewriting recursive algorithm to memoized algorithm

Question

I have written the following recursive algorithm:

p = [2,3,2,1,4]

def fn(c,i):
    if(c < 0 or i < 0):
        return 0
    if(c == 0):
        return 1
    return fn(c,i-1)+fn(c-p[i-1],i-1)

Its a solution to a problem where you have c coins, and you have to find out have many ways you can spend your c coins on beers. There are n different beers, only one of each beer. i is denoted as the i'th beer, with the price of p[i], the prices are stored in array p. The algorithm recursively calls itself, and if c == 0, it returns 1, as it has found a valid permutation. If c or i is less than 0, it returns 0 as it's not a valid permutation, as it exceeds the amount of coins available.

Now I need to rewrite the algorithm as a Memoized algorithm. This is my first time trying this, so I'm a little confused on how to do it.

Ive been trying different stuff, my latest try is the following code:

p = [2,3,2,1,4]
prev = np.empty([5, 5])
def fni(c,i):
    if(prev[c][i] != None):
        return prev[c][i]

    if(c < 0 or i < 0):
        prev[c][i] = 0
        return 0

    if(c == 0):
        prev[c][i] = 1
        return 1

    prev[c][i] = fni(c,i-1)+fni(c-p[i-1],i-1)
    return prev[c][i]

"Surprisingly" it doesn't work, and im sure it's completely wrong. My thought was to save the results of the recursive call in an 2d array of 5x5, and check in the start if the result is already saved in the array, and if it is just return it. I only provided my above attempt to show something, so don't take the code too seriously.

My prev array is all 0's, and should be values of null so just ignore that.

My task is actually only to solve it as pseudocode, but I thought it would be easier to write it as code to make sure that it would actually work, so pseudo code would help as well. I hope I have provided enough information, else feel free to ask!

EDIT: I forgot to mention that I have 5 coins, and 5 different beers (one of each beer). So c = 5, and i = 5

I forgot to mention that I have 5 coins, and 5 different beers (one of each beer). So c = 5, and i = 5. — ninjarubberband, Feb 27 '22 at 16:19
An easy way to turn a recursive function into a memoized recursive function is to stick `@functools.lru_cache` on it. — Samwise, Feb 27 '22 at 16:23
That's neat @Samwise! Though I have to write it as pseudocode in the end so I'm not sure I'm allowed to use it.. — ninjarubberband, Feb 27 '22 at 16:28

score 0 · Answer 1 · answered Feb 27 '22 at 16:37

First, np.empty() by default gives an array of uninitialized values, not Nones, as the documentation points out:

>>> np.empty([2, 2])
array([[ -9.74499359e+001,   6.69583040e-309],
       [  2.13182611e-314,   3.06959433e-309]])         #uninitialized

Secondly, although this is more subjective, you should default to using dictionaries for memoization in Python. Arrays may be more efficient if you know you'll actually memoize most of the possible values, but it can be hard to tell that ahead of time. At the very least, make sure your array values are initialized. It's good that you're using numpy-- that will help you avoid the common beginner mistake of writing memo = [[0]*5]*5.

Thirdly, you should perform checks for 'out of bounds' or negative parameters (c < 0 or i < 0) before you use them to access an array as in prev[c][i] != None. Negative indices in Python could map you to a different memoized parameter's value.

Besides those details, your memoization code and strategy is sound.

Rewriting recursive algorithm to memoized algorithm

1 Answers1