CODEWITHSUNDEEP
pythonmemoization
user3210483
user3210483

Reputation: 1

Python - Changing to Memoization

I've coded a function that finds all changes of n using the given coins when order makes a change.

def find_change(n, coins):
    if n < 0:
        return []

    if n == 0:
        return [[]]

    all_changes = []

    for last_used_coin in coins:
        curr_changes = find_change(n - last_used_coin, coins)

        for change in curr_changes:
            change.append(last_used_coin)

        all_changes.extend(curr_changes)

    return all_changes

print find_change(4, [1,2,3])

The code above is "normal" and now I want to code it again but as a memo. The values that will be saved in the memo are mutable therefore I should use deepcopy but I don't know how to use it. Can someone show me how?

EDIT: idea how to use deepcopy:

from copy import deepcopy
lst1 =[[1], [2]]
lst 2 = deepcopy(lst1)
print lst

and we get:

[[1], [2], [3]]

Upvotes: 0

Views: 195

Answers (1)

Blender
Blender

Reputation: 298136

Your only changing argument is n, so just use it as the key for your lookup table:

if n not in cache:
    ...

You could even turn it into a decorator:

def memoized(function):
    cache = {}

    def inner(n, coins):
        if n not in cache:
            cache[n] = function(n, coins)

        return cache[n]

    return inner

@memoized
def find_change(n, coins):
    ...

Upvotes: 2

Related Questions