From 42b954fb8365969c979c5cd1f3c1cd9ed1f7ffc9 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Mon, 17 Dec 2018 21:36:34 -0600
Subject: Coin change Dynamic Programming done!

---
 .../sources/coin_change_dynamic_programming.py       | 20 ++++++++++++++++++++
 .../tests/coin_change_dynamic_programmingTest.py     | 20 ++++++++++++++++++++
 2 files changed, 40 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/coin_change_dynamic_programming.py
 create mode 100644 AlgoDesignAndTechniqueEdxPython/tests/coin_change_dynamic_programmingTest.py

diff --git a/AlgoDesignAndTechniqueEdxPython/sources/coin_change_dynamic_programming.py b/AlgoDesignAndTechniqueEdxPython/sources/coin_change_dynamic_programming.py
new file mode 100644
index 0000000..f8aabd3
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/coin_change_dynamic_programming.py
@@ -0,0 +1,20 @@
+# Uses python3
+import sys
+
+
+def getChange(money):
+    denominations = [1, 3, 4]
+    minNumCoins = [0] * (money + 1)
+    for m in range(1, len(minNumCoins)):
+        minNumCoins[m] = float('inf')
+        for i in range(len(denominations)):
+            if m >= denominations[i]:
+                numCoins = minNumCoins[m - denominations[i]] + 1
+                if numCoins < minNumCoins[m]:
+                    minNumCoins[m] = numCoins
+    return minNumCoins[money]
+
+
+if __name__ == '__main__':
+    m = int(sys.stdin.read())
+    print(getChange(m))
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/coin_change_dynamic_programmingTest.py b/AlgoDesignAndTechniqueEdxPython/tests/coin_change_dynamic_programmingTest.py
new file mode 100644
index 0000000..9e1f931
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/tests/coin_change_dynamic_programmingTest.py
@@ -0,0 +1,20 @@
+'''
+Created on Dec 17, 2018
+
+@author: haidong
+'''
+import unittest
+
+from sources.coin_change_dynamic_programming import getChange
+
+class Test(unittest.TestCase):
+
+
+    def testName(self):
+        self.assertEqual(2, getChange(2))
+        self.assertEqual(9, getChange(34))
+
+
+if __name__ == "__main__":
+    #import sys;sys.argv = ['', 'Test.testName']
+    unittest.main()
\ No newline at end of file
-- 
cgit v1.2.3