1 files changed, 20 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))