Python program to implement Matrix Chain Multiplication using Dynamic Approach

# MATRIX CHAIN MULTIPLICATION using DYNAMIC PROGRAMMING

class bracket:
    lbrac=0
    rbrac=0


B=[]    # 1D matrix
n=0
A=[]    # 2D matrix
P=[]    # 1D matrix
flag=[] # 1D matrix


def getdata():
    global B
    global n
    global A
    global P
    global flag 

    n=int(input("Enter no. of matrices: "))
    n=n+1
    # Dynamic 2D matrix allocation
    for i in range(n):
        A.append([])
        for j in range(n):
            A[i].append([])

    # Dynamic 1D matrix allocation
    for i in range(n):
        P.append([])
        flag.append([])
        B.append(bracket())  

    # Assigning values to matrices
    print("Enter dimension string of matrices: ")
    for i in range(n):
        P[i]=int(input())    
    
    for i in range(n):
        for j in range(n):
            A[i][j]=0

    for i in range(1, n):
        A[0][i]=i
        A[i][0]=i   


def showdata():
    print("\nCalculation Table: \n")
    for i in range(n):
        for j in range(n):
            print("\t",A[i][j],end="")
        print("\n")
    
    print("\nK:")
    for i in range(1,n):
        print("\t",flag[i],end="")

    for i in range(n-1, 0, -1):
        k=flag[i]
        if k != 0:
            B[k+1].lbrac+=1
            B[i].rbrac+=1
            B[k].rbrac+=1
            B[1].lbrac+=1

    print("\n")
    for i in range(1, n):
        j=0
        while j<B[i].lbrac:
            print("( ",end="")
            j=j+1

        print("M",i," ",end="")

        j=0
        while j<B[i].rbrac:
            print(") ",end="")
            j=j+1
    print("\n")


def calculation():
    i=0 #declaring i
    for r in range(n):
        i=1
        for j in range(r+1, n):
            if i==j:
                A[i][j]=0
                if j==r+1:
                    flag[j]=0
            else:                
                fPointer=i;
                minimum=A[i][i]+A[i+1][j] + P[i-1] * P[i] * P[j]

                for k in range(i+1, j):
                    temp=A[i][k]+A[k+1][j] + P[i-1] * P[k] * P[j]
                    if temp<minimum:
                        minimum=temp
                        fPointer=k
                    
                A[i][j]=minimum
                if j==r+1:
                    flag[j]=fPointer
            
            i=i+1


# __________________________ Main Block Starts __________________________
print("\t\t\t____MATRIX CHAIN MULTIPLICATION____")
getdata()
calculation()
showdata()

Output