This notebook was prepared by Donne Martin. Source and license info is on GitHub.
We'll use top down dynamic programming with memoization.
total: 5 coins: [1,2,3] memo key: total value: min ways memo = { 1: 1, 2: 1, 3: 1, 4: 2, 5: 2 } 5 1, 2, 3 / 4 1, 2, 3 / 3 1, 2, 3 / \ \____ 2 1 0 1, 2, 3 1, 2, 3 / | 1 0 1, 2, 3 / 0
Complexity:
import sys
class CoinChanger(object):
def make_change(self, coins, total):
if coins is None or total is None:
raise TypeError('coins or total cannot be None')
if not coins or total == 0:
return 0
cache = {}
return self._make_change(coins, total, cache)
def _make_change(self, coins, total, cache):
if total == 0:
return 0
if total in cache:
return cache[total]
min_ways = sys.maxsize
for coin in coins:
if total - coin < 0:
continue
ways = self._make_change(coins, total - coin, cache)
if ways < min_ways:
min_ways = ways
cache[total] = min_ways + 1
return cache[total]
%%writefile test_coin_change_min.py
import unittest
class TestCoinChange(unittest.TestCase):
def test_coin_change(self):
coin_changer = CoinChanger()
self.assertRaises(TypeError, coin_changer.make_change, None, None)
self.assertEqual(coin_changer.make_change([], 0), 0)
self.assertEqual(coin_changer.make_change([1, 2, 3], 5), 2)
self.assertEqual(coin_changer.make_change([3, 2, 1], 5), 2)
self.assertEqual(coin_changer.make_change([3, 2, 1], 8), 3)
print('Success: test_coin_change')
def main():
test = TestCoinChange()
test.test_coin_change()
if __name__ == '__main__':
main()
Overwriting test_coin_change_min.py
%run -i test_coin_change_min.py
Success: test_coin_change