矩阵相乘最优计算次序和最少计算次数

矩阵相乘的最优计算次序问题可以使用动态规划算法来解决。

设矩阵序列为A1,A2,...,An，矩阵Ai的维数为pi-1 * pi，i=1,2,...,n

定义m[i][j]表示Ai到Aj的最优计算次序所需的最少计算次数，其中i<=j

则可以得到以下递归式：

当i=j时，m[i][j]=0

当i<j时，m[i][j]=min{m[i][k]+m[k+1][j]+pi-1 * pk * pj}，其中i<=k<j

最终的最少计算次数为m[1][n]

算法实现：

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

2. 枚举区间长度k=2,3,...,n，计算m[i][i+k-1]，i=1,2,...,n-k+1

3. 返回m[1][n]即为最少计算次数

4. 为了记录最优计算次序，可以在递归计算m[i][j]时，记录达到最优解时的k值，然后根据k值将问题拆分成两个子问题，分别递归求解

时间复杂度为O(n^3)