dtroupe18 · May 17, 2016 16:07 · May 17, 2016
diff --git a/DP_MatrixMultiplication.py b/DP_MatrixMultiplication.py
@@ -0,0 +1,34 @@
+# p = an array of numbers, where p[i] represents the side length of a matrix
+# example p = [5, 2, 3] 5 x 2 and 2 x 3 matrix in that order
+
+
+def MatrixChainMult(p):
+    n = len(p) - 1 # number of matrices in our multiplication problem
+
+    cost = [[0 for i in range(n)] for j in range(n)]
+    # creates and n x n matrix, we could use (n-1)x(n-1) matrix
+
+    # Length = number of matrices to consider
+
+    for length in range(2, n + 1):
+        # start = 0 index
+        for start in range(n - length + 1):
+            # end = the 0 index of the end matrix
+            end = start + length - 1
+            cost[start][end] = float('inf')
+
+            for midpoint in range(start, end):
+                possible_cost = cost[start][midpoint] + cost[midpoint + 1][end] + \
+                                p[start] * p[midpoint + 1] * p[end + 1]
+                cost[start][end] = min(cost[start][end], possible_cost)
+
+    return cost[0][n - 1]
+
+
+# test
+
+# start out by representing the matrices at a list
+p = [5, 2, 3, 6, 2]
+
+MatrixChainMult(p)
+
No results found