Working and in DP

PriyankaKhire · PriyankaKhire · commit ae2f00b5d882 · 2017-07-09T18:45:27.000-07:00
diff --git a/CoinChangeSet2.py b/CoinChangeSet2.py
@@ -0,0 +1,36 @@
+#Find minimum number of coins that make a given value
+#Given a value V, if we want to make change for V cents, and we have infinite supply
+#of each of C = { C1, C2, .. , Cm} valued coins, what is the minimum number of coins to make the change?
+def createMatrix(n, s):
+    m = [[ 0 for col in range(n+1)] for row in range(len(s)+1)]
+    return m
+
+def foo(n, s):
+    matrix = createMatrix(n,s)
+    for row in range(len(s)):
+        for col in range(n+1):
+            if(s[row] == col):
+                matrix[row+1][col] = 1
+            elif(s[row] > col):
+                #Copy the value from top
+                matrix[row+1][col] = matrix[row][col]
+            else:
+                #Get the value from those many steps behind
+                value = matrix[row+1][col - s[row]]
+                #If this value is 0 then get the value form top
+                if value == 0:
+                    matrix[row+1][col] = matrix[row][col]
+                if(value > 0):
+                    #Find top value
+                    top = matrix[row][col]
+                    if top == 0:
+                        matrix[row+1][col] = value+1
+                    else:
+                        matrix[row+1][col] = min(top, value+1)
+    print matrix
+    print "we need a minimum of "+str(matrix[len(s)][n])
+
+#Main Program
+foo(10, [2,5,3,6])
+foo(30, [25, 10, 5])
+foo(11, [9, 6, 5, 1])
