给定n个矩阵{A1,A2,…,如何确 定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。例如,给定三个连乘矩阵{A1,A2,A3}的维数 数组p为:10,100,5,50,即分别是10 ×100,100×5和5×50,

该问题可以使用动态规划来解决。首先定义一个二维数组m[i,j]存储Ai到Aj连乘积的最小数乘次数。然后定义一个二维数组s[i,j]存储在Ai到Aj中最优的断点k。

具体的算法步骤如下：

1. 对于只有一个矩阵Ai，m[i,i] = 0

2. 对于连乘长度大于1的子问题，按照子问题长度递增的顺序计算m[i,j]。假设当前考虑的子问题长度为len，i到j的区间为[l,r]，则m[l,r]可以通过以下方式求解：

- 首先将[l,r]分成两个长度分别为k和len-k的区间：[l,l+k-1] 和 [l+k,r]

- 然后计算 Ai到Ak 的最小数乘次数 m[i,k] 和 Ak+1到Aj 的最小数乘次数 m[k+1,j]

- 最后计算整个区间[l,r]的最小数乘次数 m[l,r] = m[i,k] + m[k+1,j] + pi-1 pk pj

- 记录最小值和断点位置

3. 重复步骤2直到计算出m[1,n]为止。此时s数组中记录的就是最优的断点位置，可以通过递归调用自身来得到最优的计算次序。

对于给定的三个矩阵{A1,A2,A3}的维数数组p为{10,100,5,50}，可以按照以上算法计算出最小的数乘次数为7500，最优的计算次序为(A1(A2A3))。