Working and in dynamic programming

PriyankaKhire · PriyankaKhire · commit b26a7f8bf88d · 2017-07-08T19:15:06.000-07:00
diff --git a/CoinChangeSet1.py b/CoinChangeSet1.py
@@ -0,0 +1,31 @@
+#Coin change
+#Given a value N, if we want to make change for N cents, and we have infinite supply
+#of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change?
+#The order of coins doesn�t matter.
+
+#For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}.
+#So output should be 4. For N = 10 and S = {2, 5, 3, 6},
+#there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.
+def createMatrix(n,s):
+    m = [[0 for col in range(n+1)] for row in range(len(s)+1)]
+    #Fill first col with 1
+    for row in range(len(s)+1):
+        m[row][0] = 1
+    return m
+
+def foo(n, s):
+    matrix = createMatrix(n, s)
+    for row in range(len(s)):
+        for col in range(n+1):
+            if(col < s[row]):
+                #Copy value from the top
+                matrix[row+1][col] = matrix[row][col]
+            else:
+                #add the value from top and s[row] steps behind
+                matrix[row+1][col] = matrix[row][col]+matrix[row+1][col-s[row]]
+    print matrix
+    print "So the total number of ways to make the change is "+str(matrix[len(s)][n])
+
+#Main Program
+foo(10, [6, 2, 5, 3])
+foo(4, [1,2,3])
