Created
May 17, 2016 16:07
-
-
Save dtroupe18/c7462131e5056f627ebd72f6bfb862c6 to your computer and use it in GitHub Desktop.
Dynamic Programming Matrix Multiplication
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # 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) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment