Dynamic Matrix Multiplication in Python

Dynamic Matrix Multiplication in Python | Here, we will discuss how to multiply matrices in Python using dynamic programming. Matrix multiplication is a binary operation that multiplies matrices, as in addition and subtraction both the matrices should be of the same size, but here in multiplication matrices need not be of the same size, but to multiply two matrices the row value of the first matrix should be equal to the column value of the second matrix. Multiplying is a bit more complex than other multiplicative operations.

Dynamic Matrix Multiplication in Python

Matrix chain multiplication (or the matrix chain ordering problem) is an optimization problem concerning the most efficient way to multiply a given sequence of matrices. The problem is not actually to perform the multiplications, but merely to decide the sequence of the matrix multiplications involved. The problem may be solved using dynamic programming.

# Python program to multiply matrices using dynamic programming

import sys
def matrixMultiply(d):
   n = len(d)
   # create the table to store solutions
   c = [[0 for x in range(n)] for x in range(n)]
 
   # length of the chain
   for length in range(2,n):
      for i in range(1,n-length+1):
         j = i+length-1
         # store a maximum integer
         c[i][j] = sys.maxsize
         
         for k in range(i,j):
            # p holds the value of multiplication cost
            p = c[i][k] + c[k+1][j] + d[i-1] * d[k] * d[j]
            #compare previous cost with p
            if p < c[i][j]:
               c[i][j] = p
   # last element of first row contains
   return c[1][n-1]

# take inputs
d = [1, 2, 3, 4, 5, 6, 7, 8, 9]

# calling function and print result
print('The minimum cost is', matrixMultiply(d))

Output:-

The minimum cost is 238

Python List Program Examples with Output

• List pop()
• List clear()
• List remove()
• del in Python

• Subtract Lists in Python
• Average of Numbers in List
• Remove item from List in Python
• Remove the First Element from List
• Remove the Last Element from List

• Delete all Elements in List
• Check for Duplicates in List
• Find Duplicates in List in Python
• Remove Special Characters From list
• Remove Duplicates from List in Python

• Remove Empty String from List
• Check if List Contains Same Elements

Python String Programs

• Check if String Contains Vowels
• Check if String Starts with Vowel 
• Remove Vowels from String in Python

• Get the First Character of String
• Get the Last Character of String
• Get First N Characters of String
• Extract Numbers From String
• Remove Character from String

• Remove First Character from String
• Remove Last Character from String
• Remove Special Characters from String
• Convert Hex String to ASCII String
• Compute Sum of Digits in a String

• Compare Strings with Ignore-case
• Convert Uppercase to Lowercase
• Convert Lowercase to Uppercase
• Count Uppercase and Lowercase 
• Print only Uppercase letters of String

• Reverse a String in Python
• Reverse Words in a String
• Reverse Each Word in a String
• Palindrome Program using For Loop

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Search