给定n个矩阵{Ag.4]…4n.]，其中相邻4;与A;是可乘的(i=0,1…,n-2)。给定第i个矩阵的行数p;(0≤i≤n-1)和最后一个矩阵的列数pm,，要求确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。可以用动态规划法求解。引入dp[]i]表示A;×Aj+1X…×A;所需要的最少数乘次数，引入s[][i]表示A;×AytX…×A;的最优结合计算顺序中的最后一次相乘在哪个矩阵的右侧断开，请自行计算状态转移方程。核心代码如下，请完成代码缺失的部分，注意每个空只填写一个关键字、运算符、标识符或表达式（注意不需要空格和其他间隔符）：void MatrixChain (int*p, int n, int**dp, int **s)，void Traceback(int i, int j, int **s)补全丰富并详细注释

这道题目是矩阵连乘问题，它是动态规划的一个经典例题。给定n个矩阵{A1, A2, ..., An}，其中相邻两个矩阵Ai和Ai+1是可乘的，即Ai的列数等于Ai+1的行数。每次矩阵乘法需要进行p[i-1] * p[i] * p[i+1]次数乘运算，其中p[i]表示第i个矩阵的行数和列数。

目标是确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。可以用动态规划法求解。引入dp[i][j]表示Ai×Ai+1×...×Aj所需要的最少数乘次数，引入s[i][j]表示Ai×Ai+1×...×Aj的最优结合计算顺序中的最后一次相乘在哪个矩阵的右侧断开。

状态转移方程为：

dp[i][j] = min{ dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j] }，其中i≤k<j

这个状态转移方程的意义是，对于每个区间[i, j]，枚举其中的断点k，计算以k为断点的最小数乘次数，然后取其中的最小值作为dp[i][j]的值。

核心代码如下：

void MatrixChain(int *p, int n, int **dp, int **s) {
    for (int r = 2; r <= n; ++r) { // 区间长度从2开始遍历
        for (int i = 1; i <= n - r + 1; ++i) { // 枚举区间左端点
            int j = i + r - 1; // 区间右端点
            dp[i][j] = INT_MAX; // 初始化为最大值
            for (int k = i; k < j; ++k) { // 枚举断点
                int t = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (t < dp[i][j]) { // 更新最小值
                    dp[i][j] = t;
                    s[i][j] = k; // 记录断点位置
                }
            }
        }
    }
}

void Traceback(int i, int j, int **s) { // 根据记录的断点位置s进行回溯
    if (i == j)
        return;
    Traceback(i, s[i][j], s);
    Traceback(s[i][j] + 1, j, s);
    std::cout << "(" << i << "," << s[i][j] << ")x(" << (s[i][j] + 1) << "," << j << ")";
}

在MatrixChain函数中，我们首先遍历区间长度r，然后枚举区间左端点i，计算区间[i, j]的最小数乘次数，最后更新dp[i][j]的值和记录最优断点位置的s[i][j]的值。

在Traceback函数中，我们根据记录的最优断点位置s进行递归回溯，输出最优的矩阵乘法次序。

由于矩阵连乘问题的时间复杂度为O(n^3)，因此使用动态规划算法进行求解能够在合理的时间内得到最优解。