用分治法求矩阵连乘最优顺序

矩阵连乘问题是指给定一组矩阵{A1,A2,A3,...,An}，求它们相乘的最优顺序，使得计算乘积的次数最少。

假设矩阵Ai的维度为pi-1 × pi，那么这组矩阵相乘的总次数为：

M(1,n) = M(1,k) + M(k+1,n) + p0pkpn （1 <= k < n）

其中，M(i,j)表示从Ai到Aj这部分矩阵相乘的最优次数。

为了求解M(1,n)，可以采用分治法的思想，将问题分解为若干个子问题，分别解决后再合并得到最终结果。

具体来说，可以将这组矩阵分成两部分：{A1,A2,...,Ak}和{Ak+1,Ak+2,...,An}，其中1 <= k < n。那么，这两部分矩阵相乘的最优次数为：

M(1,k) 和 M(k+1,n)

而这两部分相乘后再与p0pkpn相乘，就得到了从A1到An这部分矩阵相乘的次数。即：

M(1,n) = M(1,k) + M(k+1,n) + p0pkpn

在实际应用中，可以采用动态规划的方式，先计算出所有的M(i,j)，再根据M(1,n)得到最终结果。具体来说，可以定义一个二维数组dp，其中dp[i][j]表示从Ai到Aj这部分矩阵相乘的最优次数。那么，可以按照以下步骤计算dp数组的值：

1. 对角线上的元素dp[i][i]均为0，因为单个矩阵相乘的次数为0。

2. 对于每个子问题，从小到大依次计算dp[i][j]的值。具体来说，可以按照以下公式计算：

dp[i][j] = min{dp[i][k] + dp[k+1][j] + pi-1 * pk * pj} (i <= k < j)

其中，k为分割点，pi-1 * pk * pj表示从Ai到Ak再从Ak+1到Aj相乘的次数。

3. 最终的结果为dp[1][n]。

时间复杂度为O(n^3)，空间复杂度为O(n^2)。