三角剖分求解矩阵链最优的算法代码

三角剖分法（Dynamic Programming）用于求解矩阵链乘法问题的典型代码如下，使用Python编写：

def matrix_chain_order(p):
    n = len(p)  # 数组长度
    dp = [[0 for _ in range(n)] for _ in range(n)]
    
    # 初始化边界条件
    for i in range(n):
        dp[i][i] = 0  # 单个矩阵无需操作
        if i < n - 1:
            dp[i][i+1] = p[i+1]  # 直接相连的两个矩阵直接相乘

    # 递归填充dp数组
    for l in range(2, n):
        for i in range(n-l):
            j = i + l
            dp[i][j] = float('inf')  # 初始状态设为无穷大
            for k in range(i, j):
                # 计算当前子问题的最优解
                cost = dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1]
                if dp[i][j] > cost:
                    dp[i][j] = cost

    # 返回最短路径
    return dp[0][n-1], get_matrix_order(dp, p)

def get_matrix_order(dp, p):
    order = []
    i, j = 0, len(p) - 1
    while i < j:
        order.append(str(p[i]))
        k = dp[i][j]
        while i + 1 < j and dp[i+1][k] == dp[i][k]:
            k -= 1
        order.append('*(')
        order.append(str(p[k+1]))
        i = k + 1
    order.append('*' if i == j else ')')
    return ''.join(order)

# 示例
p = [10, 100, 5, 50, 30, 20, 60, 45, 50]
cost, order = matrix_chain_order(p)
print(f"最小成本: {cost}")
print(f"最优括号顺序: {order}")

这个代码首先初始化了一个二维动态规划表 `dp`，然后递归地计算了所有子问题的最优解，并在最后返回了整个问题的最小成本以及相应的括号顺序。