给定n个矩阵：a1,a2,…,an，其中ai与ai+1是可乘的，i=1，2…，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出

### 回答1：
矩阵连乘积的最小数乘次数。这是一个经典的动态规划问题，可以使用动态规划算法来解决。具体来说，可以定义一个二维数组dp，其中dp[i][j]表示计算从第i个矩阵到第j个矩阵的连乘积所需的最小数乘次数。然后，可以使用递推公式dp[i][j] = min{dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]}，其中p是矩阵的规模数组，k的取值范围是[i,j-1]。最终的答案就是dp[1][n]。

### 回答2：
该问题可以通过动态规划算法来解决。思路是将矩阵连乘问题拆分为子问题，从小规模的子问题逐步求解，最终得到全局最优解。

定义状态：设m[i][j]为计算Ai到Aj的最小数乘次数。

状态转移方程：

当i=j时，m[i][j]=0；
当i<j时，m[i][j]=min{m[i][k]+m[k+1][j]+P[i-1]*P[k]*P[j]}(i<=k<j)，其中P[i-1]*P[k]*P[j]为矩阵Ai到Aj相乘的次数。

算法实现：

1. 初始化m[i][i]=0，i=1,2,...,n。

2. 逐步求解规模从小到大的子问题，对于规模为len的子问题，枚举起始矩阵的位置i，计算m[i][i+len-1]的值。

3. 最后，m[1][n]即为计算矩阵连乘积所需的最小数乘次数。

代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1000;
int m[MAXN][MAXN], p[MAXN];

int main()
{
int n;
cin >> n;
for (int i = 0; i <= n; i++)
cin >> p[i];

memset(m, 0, sizeof(m));

for (int len = 2; len <= n; len++) //枚举子问题规模
{
for (int i = 1; i <= n - len + 1; i++) //枚举起始矩阵位置
{
int j = i + len - 1;
m[i][j] = 1 << 30; //初始化为一个较大的值
for (int k = i; k < j; k++) //枚举划分点
{
int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (t < m[i][j])
m[i][j] = t; //更新最小值
}
}
}

cout << m[1][n] << endl;
return 0;
}

### 回答3：
矩阵连乘问题是一道经典的动态规划问题，其最优次序问题可以用动态规划求解。设矩阵ai的维数为pi-1×pi（i=1，2…，n），矩阵链的乘积为A1A2…An，其中Ai的维数为pi-1×pi（i=1，2…，n），则对于相邻的两个矩阵，它们可以按照任意顺序进行乘法运算，但其结果却是不同的。如(A1A2)A3与A1(A2A3)是两种不同的计算次序，其所需的乘法次数也不同。

通过观察可以发现，计算A1A2…An的数乘次数可以拆分成计算A1A2…Ak和计算Ak+1Ak+2…An之后再进行合并得到的。因此我们可以设计动态规划状态f[i][j]表示计算A iAi+1…Aj所需的最少数乘次数，则我们需要求出f[1][n]。

接下来考虑如何求解状态转移方程。对于i≤k<j，要计算A iAi+1…Ak和A k+1Ak+2…Aj的乘积，其计算次序有多种，我们需要选择其中乘法次数最少的一种，并将其作为计算f[i][j]的中间结果。因此状态转移方程为：

f[i][j]=min(f[i][k]+f[k+1][j]+pi-1pkpj)(i≤j，i<k<j)

计算此状态转移方程的时间复杂度为O(n3)，并且我们可以通过记录每一次最优的k值来还原出具体计算次序。因此，矩阵连乘问题可以通过动态规划求解，其时间复杂度为O(n3)，可以高效地求解较大规模的矩阵连乘问题。