矩阵链乘法 自顶向下 自底向上 Python 实现 算法导论

def Memoized_Matrix_chain(p):
    n = len(p)
    m = [[0 for i in range(n)] for j in range(n)]
    s = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            m[i][j] = float('inf')
    return lookup_chain(m, p, 1, n - 1, s), s


def lookup_chain(m, p, i, j, s):
    if m[i][j] < float('-inf'):
        return m[i][j]
    if i == j:
        m[i][j] = 0
    else:
        for k in range(i, j):
            q = lookup_chain(m, p, i, k, s) + lookup_chain(m, p, k + 1, j, s) + p[i - 1] * p[k] * p[j]
            if q < m[i][j]:
                m[i][j] = q
                s[i][j] = k
    return m[i][j]


def Print_Optimal_Oarens(s, i, j):
    if i == j:
        print("A", i, end="   ")
    else:
        # print("(", end="")
        print("(", end="")
        Print_Optimal_Oarens(s, i, s[i][j])
        Print_Optimal_Oarens(s, s[i][j] + 1, j)
        print(")", end="")


p = [30, 35, 15, 5, 10, 20, 25]
n, m = Memoized_Matrix_chain(p)
Print_Optimal_Oarens(m, 1, 6)
print()

def Maxtrix_Chain_order(p):
    '''
    :param p:P list is cost of Matrix
    :return: return the list of m and s m is cost of matrix
    S is a copy of matrix ' cost
    '''
    n=len(p) # len n 不用减一 因为Python for循环 右边界
    m=[[0 for i in range(n)] for j in range(n) ]
    s=[[0 for i in range(n)] for j in range(n) ]
    for l in range(2,n):
        for i in range(1,n-l+1):
            j=i+l-1
            m[i][j]=123123123123
            for k in range(i,j):
                q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]
                if q