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

Question

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)

Answer 1

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.