出题人： 描述 有n个矩阵，大小分别为 a0*a1, a1*a2, a2*a3, ..., a[n-1]*a[n] 现要将它们依次相乘，只能使用结合率，求最少需要多少次运算。 　　两个大小分别为p x q和q x r的矩阵相乘时的运算次数计为p x q x r。 输入描述 输入的第一行包含一个整数n，表示矩阵的个数。 第二行包含n+1个数，表示给定的矩阵。 输出描述 输出一个整数，表示最少的运算次数。 用例输入 1 3 1 10 5 20 用例输出 1 150 提示 1<=n<=1000, 1<=ai<=10000。c++

```cpp #include <iostream> #include <vector> #include <climits> using namespace std; int matrixChainMultiplication(vector<int>& a) { int n = a.size() - 1; // 创建二维数组dp，dp[i][j]表示从第i个矩阵到第j个矩阵相乘所需的最少运算次数 vector<vector<int>> dp(n, vector<int>(n, 0)); // 链长从2开始递增，因为链长为1时不需要运算 for (int chainLength = 2; chainLength <= n; ++chainLength) { for (int i = 0; i <= n - chainLength; ++i) { int j = i + chainLength - 1; dp[i][j] = INT_MAX; // 尝试所有可能的分割点 for (int k = i; k < j; ++k) { int cost = dp[i][k] + dp[k + 1][j] + a[i] * a[k + 1] * a[j + 1]; if (cost < dp[i][j]) { dp[i][j] = cost; } } } } return dp[0][n - 1]; } int main() { int n; cin >> n; vector<int> a(n + 1); for (int i = 0; i <= n; ++i) { cin >> a[i]; } cout << matrixChainMultiplication(a) << endl; return 0; } ``` 代码解释： 1. 输入处理：首先读取矩阵的个数`n`，然后读取`n + 1`个整数存储在向量`a`中，这些整数表示矩阵的维度。 2. 动态规划数组：创建一个二维数组`dp`，其中`dp[i][j]`表示从第`i`个矩阵到第`j`个矩阵相乘所需的最少运算次数。 3. 链长递增：通过外层循环控制链长从2开始递增，因为链长为1时不需要运算。 4. 分割点尝试：对于每个链长，内层循环确定起始矩阵`i`和结束矩阵`j`，然后尝试所有可能的分割点`k`，计算不同分割方式下的运算次数，取最小值更新`dp[i][j]`。 5. 输出结果：最终`dp[0][n - 1]`即为从第1个矩阵到第`n`个矩阵相乘所需的最少运算次数。 复杂度分析： - 时间复杂度：$O(n^3)$，因为有三层嵌套循环。 - 空间复杂度：$O(n^2)$，主要用于存储二维数组`dp`。 [2026-02-02 17:21:40 | AI问答 | 644点数解答]