给定n个矩阵a1,a2,…,an动态规划法

给定n个矩阵a1,a2,…,an，它们的维度分别为p0*p1,p1*p2,…,pn-1*pn，假设它们可以按照不同的顺序进行乘法运算，求最少需要进行多少次乘法运算才能将它们全部相乘。

这是一个经典的矩阵链乘法问题，可以使用动态规划来求解。设m[i][j]表示从矩阵ai到矩阵aj的最少乘法次数，则有以下递推式：

m[i][j] = 0, i=j
m[i][j] = min{m[i][k]+m[k+1][j]+pi-1 * pk * pj}，i<=k<j

其中pi-1 * pk * pj表示矩阵ai到aj的乘法次数，k表示在i和j之间的分割点。根据上述递推式，我们可以使用动态规划算法来计算出m[1][n]的值，即为所求的最少乘法次数。

具体实现时，可以使用二维数组m来存储中间结果，使用两个循环来枚举子问题的规模，并在内部循环中枚举分割点k，根据递推式计算出m[i][j]的值。最终，m[1][n]的值即为最少乘法次数。

下面是使用Python实现的代码示例：

def matrix_chain_order(p):
    n = len(p) - 1
    m = [[0] * (n + 1) for _ in range(n + 1)]
    for l in range(2, n + 1):
        for i in range(1, n - l + 2):
            j = i + l - 1
            m[i][j] = float('inf')
            for k in range(i, j):
                q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]
                if q < m[i][j]:
                    m[i][j] = q
    return m[1][n]

其中，p是一个数组，表示每个矩阵的维度。例如，p=[50, 10, 20, 5, 80]表示有4个矩阵，它们的维度分别为50*10、10*20、20*5和5*80。调用matrix_chain_order(p)函数即可求出最少乘法次数。