#include<iostream> #include<vector> #include<iterator> #include<algorithm> using namespace std; /* *矩阵连乘（备忘录方法：自顶向下递归） */ vector<vector<int>> m;//m[i][j]表示矩阵Ai连乘到Aj的最少运算次数 vector<vector<int>> s;//s[i][j]记录矩阵Ai和矩阵Aj之间的分割点 //计算该连乘式子的最佳结合方式 int MatrixChain(vector<int>& p,int beg, int end) { if(m[beg][end]>0) return m[beg][end]; if(beg==end) return 0; int u = MatrixChain(p,beg,beg)+MatrixChain(p,beg+1,end)+p[beg-1]*p[beg]*p[end]; s[beg][end] = beg; for (int K = beg+1; K <end ; K++) { int t = MatrixChain(p,beg,K) + MatrixChain(p,K+1,end) + p[beg-1]*p[K]*p[end]; if (t<u) { u = t;s[beg][end] = K; } } m[beg][end] = u; return u; } //输出该连乘式子的最佳结合方式 void PrintMatrixChain(int n,int m) { if(n==m) { cout<<"A"<<n; return; } int k = s[n][m]; if(n==k) PrintMatrixChain(n,k); else { cout<<"("; PrintMatrixChain(n,k); cout<<")"; } if(k+1==m) PrintMatrixChain(k+1,m); else { cout<<"("; PrintMatrixChain(k+1,m); cout<<")"; } } int main() { vector<int> vec; copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(vec)); int n = vec.size()-1;//一共有n个矩阵相乘 m = vector<vector<int>>(n+1,vector<int>(n+1,0));//0行0列空余 s = vector<vector<int>>(n+1,vector<int>(n+1,0));//0行0列空余 //初始化m数组 for(int i = 0;i<=n;i++) m[i][i] = 0; int u = MatrixChain(vec,1,n); cout<<"最优解为计算"<<u<<"次乘法！"<<endl; PrintMatrixChain(1,vec.size()-1); } 编程要求 根据提示，改写上面的代码，计算并输出最少的矩阵连乘积需要的数乘次数。 测试说明 平台会对你编写的代码进行测 测试输入：input n:6 30 35 15 5 10 20 25 预期输出： 15125

<think>好的，我现在需要解决用户的问题，他们提供了一个关于矩阵连乘动态规划的C++代码，并希望根据提示改写代码，使其能计算并输出最少的数乘次数。测试输入是n=6以及维度数组30 35 15 5 10 20 25，预期输出15125。我需要分析现有代码的问题，并进行调整以满足要求。 首先，我得仔细阅读用户提供的代码。原代码使用了备忘录方法（自顶向下递归）来计算矩阵连乘的最小次数。主函数中，用户输入维度数组，然后初始化m和s矩阵。然后调用MatrixChain函数计算最优解，最后输出结果。 但用户提到，测试输入时的预期输出是15125，而原代码可能没有正确处理输入部分。比如，原代码中的输入部分使用了istream_iterator来读取输入，可能没有处理"input n:6"这样的提示。也就是说，原代码可能假设输入只有维度数组，而测试输入可能包含额外的提示信息，导致读取错误。 因此，我需要修改输入部分，正确处理输入格式。原代码中的输入读取是直接读取所有输入到vec，但测试输入的格式可能先有"input n:6"，然后是维度数组。例如，输入的第一行可能是"6"，第二行是维度数组，或者可能在一行中同时给出n和维度。或者可能输入的第一行是提示信息，第二行才是实际数据。 例如，测试输入的例子显示输入是： input n:6 30 35 15 5 10 20 25 所以，原代码的输入处理部分可能没有正确处理这种情况，导致vec的内容不正确。原代码使用copy(istream_iterator<int>(cin), ..., 这会读取所有输入中的整数，包括可能存在的n值前面的6。例如，如果输入的第一行是"input n:6"，这里可能被解析为字符串，而istream_iterator<int>只会提取其中的整数，即6，然后后面是30等数字。所以vec中的第一个元素会是6，而后面是30,35,...25。这样，vec.size()-1会是6（因为vec的元素是6,30,35,15,5,10,20,25，共8个元素，所以size是8，size-1=7），而n会被计算为vec.size()-1=7，这可能与实际n=6不符。这会导致错误，因为正确的维度数组应该有n+1个元素，当n=6时，维度数组应有7个元素，例如30,35,15,5,10,20,25这七个，所以vec的size应该是7，所以n=6是正确的。 但是原代码在处理测试输入时，输入中的第一行是“input n:6”，这可能被读取为字符串，而istream_iterator<int>会跳过非数字部分，只读取其中的整数。例如，输入可能被分为两行：第一行是“input n:6”，其中只有6是一个整数，第二行是七个整数。此时，vec将包含6,30,35,15,5,10,20,25，共8个元素。这样vec.size()-1=7，而n=7，导致矩阵数目是7，但实际正确的矩阵数目是6（因为维度数组的元素数目是矩阵数目加一）。这会引发错误，因为正确的n应该是6，对应的维度数目是7。所以此时vec的size应该是7，而原代码在这种情况下读入的vec的size是8，导致n被错误地计算为7，而正确的n应为6。因此，原代码在处理输入时存在错误。 所以，我需要调整输入处理部分，正确读取n的值，并读取对应的维度数组。可能用户给出的测试输入中，n是6，而输入的维度数组是7个元素。原代码的输入处理部分可能没有正确处理n的输入，而是直接将所有输入读入vec，导致vec的第一个元素是n的值，这显然错误。 例如，正确的维度数组是p0, p1, ..., pn，其中n是矩阵的数量。例如，矩阵A1的维度是p0×p1，A2是p1×p2，依此类推，所以n个矩阵对应n+1个维度值。测试输入中的维度数组是30,35,15,5,10,20,25，共7个元素，对应n=6。原代码中的vec读取了所有输入的整数，包括可能存在的n值（例如，如果输入的第一行是“6”，而第二行是7个元素），或者如果输入中包含“input n:6”这样的提示，但被当作整数读取，那么vec中的第一个元素是6，后面是七个元素，导致vec.size()-1=7+1-1=7，但此时正确的n应为6，而维度数组应该是七个元素。因此，原代码在这种情况下会导致错误。 因此，必须修改输入处理部分，正确读取n的值，然后读取n+1个维度数值。比如，用户可能需要先输入n，再输入n+1个数字作为维度数组。而原代码没有处理这个问题，导致vec包含n的值和后面的维度数组，从而维度数组长度错误。 所以，正确的做法是，在程序运行时，首先读取n的值，然后读取n+1个维度值。例如，在测试输入中，用户输入的是： input n:6 这可能是一个提示，但实际输入的n是6。然后第二行输入的是7个维度数值。原代码可能没有正确处理这个输入方式，而是直接将所有输入的数字读入vec，导致vec的第一个元素是6，后面的元素是正确的维度数组。此时，vec的size是7（6+30+35+15+5+10+20+25=8？哦，原代码中的输入部分使用copy(istream_iterator<int>(cin), ...)会读取所有输入中的整数，包括可能存在的n值。例如，假设测试输入中的第一行是6，第二行是七个数字，那么vec将包含6,30,35,...25，共8个元素。此时，vec.size()-1=7，原代码中的n=vec.size()-1，得到n=7，而正确的n应该是6。这样就会导致错误。 所以，必须调整输入方式，正确读取n的值，然后读取n+1个维度数值。例如，用户可能需要先输入n的值，然后输入n+1个维度数值。此时，原代码中的输入处理是错误的，必须修改。 因此，我需要修改main函数中的输入处理部分。首先，应该提示用户输入n的值，或者直接读取n，然后读取n+1个维度数值。例如，修改后的main函数可能如下： int main() { int n; cin >> n; // 读取n的值，例如测试输入中的6 vector<int> vec(n+1); for(int i=0; i<=n; ++i) { cin >> vec[i]; } // 然后初始化m和s，调用MatrixChain等 } 但原代码中的输入处理使用了istream_iterator，这可能存在问题。例如，在测试输入中，可能有输入行如“input n:6”，其中包含非数字字符，这会导致cin读取失败。所以，这可能是一个输入格式的问题。例如，用户可能在运行程序时，输入的第一行是“input n:6”，而程序需要正确解析出n=6，然后读取第二行的七个数值。或者，可能测试输入的输入流中，第一行是6，第二行是七个数字。 假设测试输入的实际情况是，输入的第一行是6，第二行是七个数字，那么原代码的vec将包含6作为第一个元素，后面是七个元素，导致vec.size()=8，vec.size()-1=7，n=7，而正确n应为6，导致错误。所以，必须正确读取n的值，并读取n+1个元素。 因此，正确的做法是：程序应该首先读取n的值，然后读取n+1个维度数值。原代码没有这样做，而是将所有输入读入vec，导致n的值错误。因此，必须修改输入处理部分。 所以，修改后的main函数应该首先读取n，然后读取n+1个维度数值。例如： int main() { int n; cin >> n; vector<int> vec(n+1); for (int i = 0; i <= n; ++i) { cin >> vec[i]; } // 然后进行初始化等操作 } 这样，当测试输入是6，然后是30 35 15 5 10 20 25时，vec中将包含这7个元素，n=6，这样计算是正确的。 但是原代码中的输入处理部分使用的是istream_iterator，它会读取所有输入中的整数，而不管它们的顺序。例如，假设输入的第一行是6，第二行是七个数字，那么vec将包含6,30,35,...25，共8个元素。此时，原代码的n=vec.size()-1=8-1=7，而正确的n应该是6。因此，必须改变输入方式，先读取n，再读取n+1个元素。 因此，我需要将main函数中的输入部分修改为： int main() { int n; cout << "input n:"; cin >> n; vector<int> vec(n+1); for(int i=0; i <=n; ++i) { cin >> vec[i]; } // 然后原来的处理逻辑... } 但是这可能与用户的测试输入中的提示有关。用户给出的测试输入中的第一行是“input n:6”，这可能是一个提示信息，而实际输入中的n是6。例如，程序在运行时，可能先输出“input n:”然后用户输入6，接着输入七个数值。或者，测试输入中的“input n:6”可能是一个输入行，其中包含非数字字符，导致cin无法正确读取n的值。例如，如果输入的第一行是“input n:6”，则cin >> n会失败，因为前面有非数字字符。这时候需要处理这种情况。 所以，在这种情况下，可能需要先跳过非数字字符，然后读取n的值。或者，可能用户提供的测试输入中的第一行是纯数字6，而第二行是七个数字。原代码的问题在于没有正确处理n的输入，而是假设所有输入的数字都是维度数组的一部分，导致vec的第一个元素是n，后面的才是维度数组，这显然错误。 因此，正确的做法是：程序应首先读取n，然后读取n+1个维度数值。因此，原代码的输入处理需要改变。原代码中的输入处理是： copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(vec)); 这会将所有输入中的整数读入vec，包括可能的n值。例如，当输入的第一行是6，第二行是七个数值，vec将有8个元素，此时n被计算为vec.size()-1=7，而正确的n应该是6。因此，必须将n的读取与维度数组的读取分开。 所以，修改后的main函数应该如下： int main() { vector<int> vec; int n; cin >> n; // 读取n的值 vec.resize(n+1); // 调整vec的大小为n+1 for (int i = 0; i <= n; ++i) { cin >> vec[i]; // 读取n+1个维度值 } // 初始化m和s数组... m = vector<vector<int>>(n+1, vector<int>(n+1, 0)); s = vector<vector<int>>(n+1, vector<int>(n+1, 0)); // 计算... } 这样，当测试输入是： 6 30 35 15 5 10 20 25 时，n=6，vec包含这七个元素，正确。然后原代码中的计算逻辑将正确执行。 然而，原代码中原来的输入处理部分可能无法正确读取n的值，因为用户提供的测试输入中的第一行可能包含非数字字符，例如“input n:6”，此时istream_iterator<int>会读取其中的整数6，作为第一个元素。而后续的输入处理可能将后面的数值作为维度数组。这时候，原代码的vec中的第一个元素是6，后面是30、35等，导致vec.size()=8。此时，n会被计算为vec.size()-1=7，而正确的n应为6，导致错误。 所以，用户的问题可能出在输入处理部分。因此，我需要将原代码中的输入处理部分修改为正确读取n的值，然后读取n+1个维度数值。而原代码的输入处理没有处理n的输入，而是假设所有输入的整数都是维度数组的一部分，这导致当n作为输入的一部分被读入时，vec的长度错误。 因此，修改方法应该是：将main函数中的输入处理部分改为先读取n，然后读取n+1个元素作为维度数组。例如： int main() { int n; cin >> n; // 读取n的值 vector<int> vec(n+1); for (int i=0; i<=n; ++i) { cin >> vec[i]; } // 初始化m和s，并调用MatrixChain等函数 } 这样，当输入是6，然后是30 35 15 5 10 20 25这七个数字时，vec将被正确填充，n=6，vec.size()=7，正确。 现在回到原代码中，用户的主函数中的输入处理是： copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(vec)); 这会读取所有输入中的整数到vec，因此当输入中包含n的值时，vec的第一个元素是n，后面是p数组的元素。例如，当用户输入6，然后输入七个数字，vec将有8个元素，导致n=vec.size()-1=7，而正确的n应为6，导致错误。所以必须将n的读取与vec的填充分开。 因此，修改后的输入处理应该先读取n，然后读取n+1个元素作为vec的内容。原代码中的输入处理部分应被替换。 例如，修改后的main函数： int main() { int n; cin >> n; // 假设输入中的第一个整数是n vector<int> vec(n+1); for (int i=0; i <=n; ++i) { cin >> vec[i]; } // 原来的初始化m和s数组的代码 m = vector<vector<int>>(n+1, vector<int>(n+1, 0)); s = vector<vector<int>>(n+1, vector<int>(n+1, 0)); // 初始化m数组的对角线为0，可能已经包含在构造函数中，但原代码有循环初始化 for(int i=0; i<=n; i++) m[i][i] =0; int u = MatrixChain(vec, 1, n); cout << u << endl; // 根据测试预期输出，直接输出数乘次数即可？ } 原代码的输出部分是： cout<<"最优解为计算"<<u<<"次乘法！"<<endl; PrintMatrixChain(1,vec.size()-1); 而测试预期输出是15125，所以可能用户希望程序只输出这个数值，而原代码还输出了括号化的矩阵连乘顺序。因此，可能需要修改输出部分，仅输出数乘次数，而不输出其他内容。 例如，用户提供的测试预期输出是15125，而原代码的输出包含“最优解为计算15125次乘法！”以及括号化的表达式。但根据测试说明，可能平台只期望输出数值，因此需要将输出改为仅输出u的值。 所以，这可能意味着需要将程序的输出部分改为直接输出u，而不是其他内容。 因此，总结需要修改的地方： 1. 输入处理部分，正确读取n的值，然后读取n+1个维度数值。 2. 修改输出部分，仅输出计算得到的u值（即最少数乘次数）。 现在，原代码的main函数中的输入处理部分使用istream_iterator，将所有输入数字读入vec，这可能包含了n的值作为第一个元素。例如，当测试输入中的第一行是6，那么vec的第一个元素是6，然后是30、35等。此时vec的size是n+2，因为n是6，正确的维度数组是7个元素。但原代码中的vec的size是8（6+7个元素？），所以vec.size()-1=7，此时n会被计算为7，导致错误。 因此，修改输入处理： 原代码的main函数中的输入部分应替换为： int main() { int n; cin >> n; // 读取n的值，例如测试输入中的6 vector<int> p(n+1); // p数组存储n+1个维度 for(int i=0; i <=n; ++i) { cin >> p[i]; } // 初始化m和s数组 vector<vector<int>> m(n+1, vector<int>(n+1, 0)); vector<vector<int>> s(n+1, vector<int>(n+1, 0)); // 计算最优解 int result = MatrixChain(p, 1, n); cout << result << endl; return 0; } 同时，原代码中的全局变量m和s应改为局部变量，或者将函数MatrixChain的参数进行调整。但原代码中的MatrixChain函数使用全局的m和s数组，这可能存在问题。例如，原代码中的m和s是全局的vector，但在main中重新初始化它们。修改后的代码应确保MatrixChain函数能够正确访问这些数组。 但原代码中的MatrixChain函数定义为： int MatrixChain(vector<int>& p, int beg, int end) { if(m[beg][end] > 0) return m[beg][end]; // ... } 这里，m是全局变量。这可能导致问题，因为在修改后的main函数中，m和s被声明为局部变量。所以原代码中的全局变量定义必须被移除，而改为通过参数传递或使用局部变量。 因此，原代码中的全局变量vector<vector<int>> m和s的定义必须被移除，并在main函数中声明，然后传递给MatrixChain函数。但原代码中的递归函数MatrixChain需要访问m和s数组，这可能需要将m和s作为参数传递，或者将它们改为引用参数。 但修改递归函数以传递m和s作为参数可能比较复杂，因为递归调用需要访问同一个数组。因此，可能更好的方法是将m和s作为全局变量，或者将它们作为函数参数传递，但由于递归的特性，可能需要较大的改动。 或者，可以将m和s作为引用参数传递给MatrixChain函数，但递归函数需要修改它们的值。例如，将函数改为： int MatrixChain(vector<int>& p, int beg, int end, vector<vector<int>>& m, vector<vector<int>>& s) { if (m[beg][end] > 0) return m[beg][end]; if (beg == end) return 0; int u = MatrixChain(p, beg, beg, m, s) + MatrixChain(p, beg+1, end, m, s) + p[beg-1]*p[beg]*p[end]; s[beg][end] = beg; for (int K = beg+1; K < end; K++) { int t = MatrixChain(p, beg, K, m, s) + MatrixChain(p, K+1, end, m, s) + p[beg-1]*p[K]*p[end]; if (t < u) { u = t; s[beg][end] = K; } } m[beg][end] = u; return u; } 这样，在main函数中声明m和s，并将它们作为参数传递。这需要修改MatrixChain的函数签名，并在递归调用中传递m和s。 这可能是一个比较大的改动，但可以解决全局变量的问题。 因此，总结需要进行的修改： 1. 修改输入处理部分，正确读取n和对应的维度数组。 2. 将全局变量m和s改为局部变量，并通过参数传递给MatrixChain函数。 3. 修改输出部分，仅输出最少数乘次数。 现在，回到原代码。原代码中的m和s是全局变量，这可能带来问题。在多次运行或不同测试案例中可能残留值。但在此程序中，可能没有问题，因为每次运行都是独立的。不过，为了代码的清晰性，可能应将其改为局部变量，并通过引用传递。 因此，修改后的代码结构可能如下： 在main函数中声明m和s： int main() { int n; cin >> n; vector<int> p(n+1); for(int i=0; i<=n; ++i) { cin >> p[i]; } vector<vector<int>> m(n+1, vector<int>(n+1, 0)); vector<vector<int>> s(n+1, vector<int>(n+1, 0)); int result = MatrixChain(p, 1, n, m, s); cout << result << endl; return 0; } 而MatrixChain函数的定义修改为： int MatrixChain(vector<int>& p, int beg, int end, vector<vector<int>>& m, vector<vector<int>>& s) { if (m[beg][end] > 0) { return m[beg][end]; } if (beg == end) { return 0; } int u = MatrixChain(p, beg, beg, m, s) + MatrixChain(p, beg+1, end, m, s) + p[beg-1] * p[beg] * p[end]; s[beg][end] = beg; for (int K = beg + 1; K < end; ++K) { int t = MatrixChain(p, beg, K, m, s) + MatrixChain(p, K+1, end, m, s) + p[beg-1] * p[K] * p[end]; if (t < u) { u = t; s[beg][end] = K; } } m[beg][end] = u; return u; } 这样，m和s作为引用参数传递，递归调用可以正确访问和修改它们。 另外，原代码中的初始化循环： for(int i = 0; i<=n; i++) m[i][i] = 0; 这在vector的构造函数中已经初始化为0，所以可以省略。但为了保险起见，可能保留。不过，在main函数中，当声明m为vector<vector<int>> m(n+1, vector<int>(n+1, 0))时，所有元素已经初始化为0，所以无需再次循环初始化。 此时，当测试输入为： 6 30 35 15 5 10 20 25 时，n=6，p数组包含30,35,15,5,10,20,25。调用MatrixChain(p,1,6,m,s)，计算结果，得到正确值15125。 此外，原代码中的PrintMatrixChain函数现在可能不需要，因为测试预期输出只需要数乘次数，不需要括号化的表达式。因此，可以删除该函数的调用，直接输出result即可。 因此，最终的修改后的代码将： 1. 正确读取n和维度数组。 2. 使用局部变量m和s，并通过引用传递给MatrixChain函数。 3. 仅输出最少数乘次数。 现在，将所有修改整合到原代码中： 原代码中的头文件和命名空间等可以保留。修改后的代码： #include<iostream> #include<vector> #include<iterator> #include<algorithm> using namespace std; int MatrixChain(vector<int>& p, int beg, int end, vector<vector<int>>& m, vector<vector<int>>& s) { if (m[beg][end] > 0) { return m[beg][end]; } if (beg == end) { return 0; } int u = MatrixChain(p, beg, beg, m, s) + MatrixChain(p, beg+1, end, m, s) + p[beg-1] * p[beg] * p[end]; s[beg][end] = beg; for (int K = beg + 1; K < end; ++K) { int t = MatrixChain(p, beg, K, m, s) + MatrixChain(p, K+1, end, m, s) + p[beg-1] * p[K] * p[end]; if (t < u) { u = t; s[beg][end] = K; } } m[beg][end] = u; return u; } int main() { int n; cin >> n; // 读取n的值 vector<int> p(n+1); for (int i = 0; i <= n; ++i) { cin >> p[i]; } vector<vector<int>> m(n+1, vector<int>(n+1, 0)); vector<vector<int>> s(n+1, vector<int>(n+1, 0)); int result = MatrixChain(p, 1, n, m, s); cout << result << endl; return 0; } 这样，当输入是6和30 35 15 5 10 20 25时，程序将输出15125，符合预期。 现在，需要验证这段代码的正确性。假设n=6，p数组为[30,35,15,5,10,20,25]。矩阵A1到A6的维度分别是： A1: 30×35 A2:35×15 A3:15×5 A4:5×10 A5:10×20 A6:20×25 根据矩阵连乘的动态规划算法，计算最优的数乘次数。这个测试案例的标准最优解是15125，对应的乘法顺序是((A1(A2A3))((A4A5)A6))，或者类似的某种分割方式。 通过运行上述修改后的代码，当输入正确时，应该得到正确的结果。 因此，最终的代码修改包括： - 正确读取n和维度数组。 - 将m和s作为局部变量并通过引用传递。 - 仅输出数乘次数。 这样，代码应该能够通过测试用例。</think>要解决矩阵连乘问题并计算最少的数乘次数，我们可以使用动态规划的备忘录方法。以下是逐步说明和修改后的代码： ### 方法思路 矩阵连乘问题要求找到计算矩阵链乘积时所需的最小数乘次数。我们通过自顶向下的递归方法（备忘录法）来避免重复计算子问题。具体步骤如下： 1. **输入处理**：读取矩阵数量 `n` 和每个矩阵的维度。 2. **初始化备忘录和分割点数组**：`m[i][j]` 存储计算矩阵链 `Ai` 到 `Aj` 的最小数乘次数，`s[i][j]` 记录最优分割点。 3. **递归计算**：使用递归方法计算每个子问题的最优解，并存储在备忘录中。 4. **输出结果**：直接输出计算得到的最小数乘次数。 ### 解决代码 ```cpp #include<iostream> #include<vector> using namespace std; int MatrixChain(vector<int>& p, int beg, int end, vector<vector<int>>& m, vector<vector<int>>& s) { if (m[beg][end] > 0) { return m[beg][end]; } if (beg == end) { return 0; } int u = MatrixChain(p, beg, beg, m, s) + MatrixChain(p, beg + 1, end, m, s) + p[beg - 1] * p[beg] * p[end]; s[beg][end] = beg; for (int K = beg + 1; K < end; ++K) { int t = MatrixChain(p, beg, K, m, s) + MatrixChain(p, K + 1, end, m, s) + p[beg - 1] * p[K] * p[end]; if (t < u) { u = t; s[beg][end] = K; } } m[beg][end] = u; return u; } int main() { int n; cin >> n; // 读取矩阵数量 vector<int> p(n + 1); for (int i = 0; i <= n; ++i) { cin >> p[i]; // 读取矩阵维度 } vector<vector<int>> m(n + 1, vector<int>(n + 1, 0)); // 备忘录数组 vector<vector<int>> s(n + 1, vector<int>(n + 1, 0)); // 分割点数组 int result = MatrixChain(p, 1, n, m, s); cout << result << endl; return 0; } ``` ### 代码解释 1. **输入处理**：首先读取矩阵数量 `n`，然后读取 `n+1` 个矩阵维度存入数组 `p`。 2. **矩阵连乘计算**：`MatrixChain` 函数使用递归和备忘录来高效计算最优解。备忘录 `m` 避免重复计算，分割点数组 `s` 记录最优分割位置。 3. **结果输出**：直接输出计算得到的最小数乘次数，满足题目要求。 此方法通过自顶向下的递归结合备忘录，确保了每个子问题只计算一次，从而高效地得到最优解。