Making change, recursively and iteratively.

make_change.py

# Use make_change_iter for the much better performing (space-wise) solution!

import collections

def make_change(amount, coins):
	"""
	Return the minimum number of coins that sum AMOUNT using coin values COINS.
	-1 if no solution exists. Recursive with memoization.
	"""
	memo = {}
	result = make_change_helper(amount, coins, memo)
	if result == float("inf"):
		return -1
	return result

def make_change_helper(amount, coins, memo):
	if amount < 0 or len(coins) == 0:
		return float("inf")
	if amount in coins:
		return 1
	inst_hash = (amount, tuple(coins))
	if inst_hash in memo:
		return memo[inst_hash]
	result = min(1 + make_change_helper(amount - coins[0], coins, memo),
					make_change_helper(amount, coins[1:], memo))
	memo[inst_hash] = result
	return result

# Dynamic Solution

def make_change_iter(amount, coins):
	"""
	Return the minimum number of coins that sum AMOUNT using coin values COINS.
	-1 if no solution exists. Dynamic programming.
	"""
	memo = collections.defaultdict(lambda: float("inf"))
	for c in coins:
		memo[c] = 1
	for i in range(1, amount + 1):
		if i not in coins:
			memo[i] = 1 + min([memo[i - c] for c in coins] + [memo[i]])
	if memo[amount] == float("inf"):
		return -1
	return memo[amount]