This notebook was prepared by Donne Martin. Source and license info is on GitHub.
We'll use a bottom-up dynamic programming approach.
The rows (i) represent the coin values. The columns (j) represent the totals. ------------------------- | 0 | 1 | 2 | 3 | 4 | 5 | ------------------------- 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 2 | 2 | 3 | 3 | 3 | 1 | 1 | 2 | 3 | 4 | 5 | ------------------------- Number of ways to get total n with coin[n] equals: * Number of ways to get total n with coin[n - 1] plus * Number of ways to get total n - coin[n] if j == 0: T[i][j] = 1 if row == 0: T[i][j] = 0 if coins[i] >= j T[i][j] = T[i - 1][j] + T[i][j - coins[i]] else: T[i][j] = T[i - 1][j] The answer will be in the bottom right corner of the matrix.
Complexity:
class CoinChanger(object):
def make_change(self, coins, total):
if coins is None or total is None:
return None
if not coins or total == 0:
return 0
coins = [0] + coins
num_rows = len(coins)
num_cols = total + 1
T = [[None] * num_cols for _ in range(num_rows)]
for i in range(num_rows):
for j in range(num_cols):
if i == 0:
T[i][j] = 0
continue
if j == 0:
T[i][j] = 1
continue
if coins[i] <= j:
T[i][j] = T[i - 1][j] + T[i][j - coins[i]]
else:
T[i][j] = T[i - 1][j]
return T[num_rows - 1][num_cols - 1]
%%writefile test_coin_change.py
import unittest
class Challenge(unittest.TestCase):
def test_coin_change(self):
coin_changer = CoinChanger()
self.assertEqual(coin_changer.make_change([1, 2], 0), 0)
self.assertEqual(coin_changer.make_change([1, 2, 3], 5), 5)
self.assertEqual(coin_changer.make_change([1, 5, 25, 50], 10), 3)
print('Success: test_coin_change')
def main():
test = Challenge()
test.test_coin_change()
if __name__ == '__main__':
main()
Overwriting test_coin_change.py
%run -i test_coin_change.py
Success: test_coin_change