用分治递归算法实现矩阵列乘

矩阵链乘法问题可以使用分治算法来解决。具体思路是将矩阵链分成两个子链，分别递归求解两个子链的最小标量乘法次数，然后合并两个子链的结果。合并的过程中，我们可以使用矩阵乘法来计算两个矩阵链的积，然后将得到的结果加上标量乘法次数即可。

以下是使用分治递归算法实现矩阵链乘法的代码示例：

def matrixChainOrder(p, i, j):
    if i == j:
        return 0, f'U{i+1}'
    else:
        minCost = float('inf')
        minParenthesis = ''
        for k in range(i, j):
            cost1, left = matrixChainOrder(p, i, k)
            cost2, right = matrixChainOrder(p, k+1, j)
            cost3 = p[i]*p[k+1]*p[j+1]
            totalCost = cost1 + cost2 + cost3
            if totalCost < minCost:
                minCost = totalCost
                minParenthesis = f'({left} x {right})'
        return minCost, minParenthesis

p = [30, 35, 15, 5, 10, 20, 25]
minCost, parenthesis = matrixChainOrder(p, 0, len(p)-2)
print(f'Minimum scalar multiplications: {minCost}')
print(f'Parenthesized matrix chain: {parenthesis}')

其中，`matrixChainOrder`函数接受矩阵链的维度列表p和链的起始和终止位置i和j，返回最小标量乘法次数和最优的加括号方式。在函数中，我们使用for循环枚举所有可能的分割点，递归求解左右两个子链的最小标量乘法次数，然后计算合并两个子链的最小标量乘法次数。最终返回最小标量乘法次数和最优的加括号方式。在上面的示例中，最小标量乘法次数为15125，加括号的方式为`((U1 x (U2 x U3)) x ((U4 x U5) x U6))`。