summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-12-17 21:36:34 -0600
committerHaidong Ji2018-12-17 21:36:34 -0600
commit42b954fb8365969c979c5cd1f3c1cd9ed1f7ffc9 (patch)
tree32472f1ee553f5822cb36dd1178c1b1fec1d06b4
parent1d6a57ac37f0c56a7639c1124be5501f699f3027 (diff)
Coin change Dynamic Programming done!
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/coin_change_dynamic_programming.py20
-rw-r--r--AlgoDesignAndTechniqueEdxPython/tests/coin_change_dynamic_programmingTest.py20
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