# Compute the number of ways a given amount (cents) can be changed

Given an infinite number of different coin types (such as pennies, nickels, dimes, quarters) find out how many ways n cents can be represented.

My code appears to work (although I am curious to know if it has any correctness issue). But I feel like the memoization I am doing is a bit inelegant. Can we do without dictionaries/maps, perhaps a dynamic programming based approach using 2d arrays? Or is that even worse in terms of time and space complexity?

Also is my code to update the memoized_sol good in terms of coding technique?

'''
Parameters:
cents: amount to get change for.
coin_vals: list of coin denominations in no particular order.

Returns:
number of ways <cents> can be changes using any number of coins from the given list
'''
def get_coin_change_count (cents, coin_vals):
memoized_sol = {}
return compute_coin_change_count(cents, coin_vals, 0, memoized_sol )

def compute_coin_change_count (rem_cents, coin_vals, coin_index, memoized_sol ):

if coin_index in memoized_sol:
if rem_cents in memoized_sol[coin_index]:
return memoized_sol[coin_index][rem_cents]
else:
memoized_sol[coin_index] = {}

if rem_cents == 0:
return 1

if coin_index >= len(coin_vals):
return 0

coin_val = coin_vals[coin_index]

i = 0
count = 0
while i*coin_val <= rem_cents:
count = count + compute_coin_change_count\
( rem_cents - i*coin_val, coin_vals, coin_index+1, memoized_sol )
i = i + 1

memoized_sol[coin_index][rem_cents] = count
return count

w = get_coin_change_count ( 37, [10, 1, 5, 25])
print (w)


I don't see any correctness issues, but it could be more idiomatic.

    if coin_index in memoized_sol:
if rem_cents in memoized_sol[coin_index]:
return memoized_sol[coin_index][rem_cents]
else:
memoized_sol[coin_index] = {}


Check out first defaultdict, and then functools.lru_cache for ways to simplify the memoisation - although note that lru_cache has a subtlety in that it doesn't like list as an argument type.

    if rem_cents == 0:
return 1

if coin_index >= len(coin_vals):
return 0


IMO these should have gone before the memoisation code, because they are non-memoised special cases. But I freely admit that this is mainly a matter of opinion. The only real difference effected would be to avoid initialising memoized_sol[len(coin_vals)].

    i = 0
count = 0
while i*coin_val <= rem_cents:
count = count + compute_coin_change_count\
( rem_cents - i*coin_val, coin_vals, coin_index+1, memoized_sol )
i = i + 1


Using sum and range this could be simplified to

count = sum(compute_coin_change_count(
surplus, coin_vals, coin_index + 1, memoized_sol)
for surplus in range(rem_cents, -1, -coin_vals[coin_index]))


(I'm not quite sure what the most Pythonesque indentation would be - I wouldn't normally follow PEP8 on maximum line lengths).

I would also be tempted to use sublists and eliminate the need for coin_index, but that depends on how you're handling memoisation.

Putting it all together, I get

from functools import lru_cache

def get_coin_change_count(cents, coin_vals):
@lru_cache(None)
def inner(remaining, idx):
if remaining == 0:
return 1

if idx == len(coin_vals):
return 0

return sum(inner(surplus, idx + 1)
for surplus in range(remaining, -1, -coin_vals[idx]))
return inner(cents, 0)

print(get_coin_change_count(37, [10, 1, 5, 25]))


and here the indentation does pass PEP8, in part because of shorter names. Note that using an inner function allows memoisation with lru_cache and allows the short name inner because its scope is restricted enough that this is sufficiently expressive.