题解 | 2024_矩阵连乘_2927

def matrix_chain_multiplication(p):
    n = len(p) - 1  # 矩阵的数量

    # dp[i][j] 表示第i个矩阵到第j个矩阵相乘的最小代价
    # 其中矩阵i的维度是 p[i-1] x p[i]
    dp = [[float("inf")] * (n + 1) for _ in range(n + 1)]

    # 初始化：单个矩阵不需要相乘
    for i in range(1, n + 1):
        dp[i][i] = 0

    # l 是链长，从2开始（至少两个矩阵相乘）
    for l in range(2, n + 1):  # 链长
        for i in range(1, n - l + 2):  # 起始位置
            j = i + l - 1  # 结束位置

            # 尝试所有可能的分割点
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
                dp[i][j] = min(dp[i][j], cost)

    return dp[1][n]


# 读取输入并运行
if __name__ == "__main__":
    import sys

    input_data = input().strip()
    p = list(map(int, input_data.split()))

    result = matrix_chain_multiplication(p)
    print(result)