Coin change Dynamic Programming done!

2 files changed, 40 insertions, 0 deletions

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