In [1]:
%matplotlib inline
import numpy, scipy, scipy.spatial, matplotlib.pyplot as plt
plt.rcParams['figure.figsize'] = (14, 2)
Given a positive value and a list of possible coin values, write a function that determines the minimum number of coins needed to achieve the input value. Example:
coins = [1, 5, 10, 25]
min_coin_sum(1) -> 1
min_coin_sum(6) -> 2 # 1*5 + 1*1
min_coin_sum(49) -> 7 # 1*25 + 2*10 + 4*1
min_coin_sum(52) -> 4 # 2*25 + 2*1
Suppose that we use the coin values [1, 5, 10, 25]
. The recursive solution to this uses the observation:
min_coin_sum(val) = 1 + min(
min_coin_sum(val-1),
min_coin_sum(val-5),
min_coin_sum(val-10),
min_coin_sum(val-25),
)
Suppose val = 49
. Notice that
49 = 48 + 1
49 = 44 + 5
49 = 39 + 10
49 = 24 + 25
In other words, 49 is achieved by adding one coin to the minimum coin total used to achieve 48, 44, 39, or 24.
Let's create a recursive solution:
In [2]:
def min_coin_sum(val, coins=None):
if coins is None:
coins = [1, 5, 10, 25]
if val == 0:
return 0
return 1 + min(min_coin_sum(val-coin) for coin in coins if val-coin >= 0)
Test:
In [4]:
coins = [1, 5, 10, 25]
print('val num_coins')
for val in (1, 6, 42, 49):
print('%3d %d' % (val, min_coin_sum(val, coins)))
Notice how it takes a little while to compute the answer to 49
? That's because the recursive solution is computing the solution to subproblems multiple times. For example, the solution to 49
uses the solutions to 44
and 39
. However, the solution to 44
itself needs the solution to 39
which it needlessly computes again from scratch.
A better solution is to use memoization by storing the answer to previous subproblems and referring to them later:
In [5]:
def min_coin_sum(val, coins=None):
if coins is None:
coins = [1, 5, 10, 25]
# Initialize table.
table = [0 for _ in range(val+1)]
# Dynamic programming.
for cur_val in range(1, val+1):
table[cur_val] = 1 + min([table[cur_val-coin] for coin in coins if cur_val-coin >= 0])
return table[val]
In [6]:
coins = [1, 5, 10, 25]
print('val num_coins')
for val in (1, 6, 42, 49, 52):
print('%3d %d' % (val, min_coin_sum(val, coins)))
Notice how this executes much faster than the fully recursive version. The time complexity is only $O(v n)$, where $v$ is the input coin value, and $n$ is the number of coin values.