给定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进行递归回溯，输出最优的矩阵乘法次序。

完整代码如下：

#include <iostream>
#include <climits>

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 << ")";
}

int main() {
    int n = 6; // 矩阵个数
    int p[] = {30, 35, 15, 5, 10, 20, 25}; // 矩阵行列数数组
    int **dp = new int*[n + 1]; // 定义dp数组
    int **s = new int*[n + 1]; // 定义s数组
    for (int i = 1; i <= n; ++i) {
        dp[i] = new int[n + 1];
        s[i] = new int[n + 1];
        dp[i][i] = 0; // 边界条件
        s[i][i] = 0; // 边界条件
    }

    MatrixChain(p, n, dp, s); // 计算dp和s数组
    std::cout << "Matrix multiplication order: ";
    Traceback(1, n, s); // 输出矩阵乘法次序

    // 释放内存
    for (int i = 1; i <= n; ++i) {
        delete[] dp[i];
        delete[] s[i];
    }
    delete[] dp;
    delete[] s;

    return 0;
}

在代码中，我们首先定义了矩阵个数n和矩阵行列数数组p。然后定义了dp和s数组，并对边界条件进行初始化。接着调用MatrixChain函数计算dp和s数组，最后调用Traceback函数输出最优矩阵乘法次序。

注意，在实际编写代码时，我们需要注意动态分配数组的内存，并在使用完毕后及时释放。