动态规划 矩阵连乘问题

矩阵连乘问题是一个经典的动态规划问题，其目的是找到最少的乘法次数，将一组矩阵相乘。

假设有 $n$ 个矩阵，分别为 $A_1,A_2,...,A_n$，其中矩阵 $A_i$ 的维度为 $p_{i-1} \times p_i$，则这一组矩阵的乘积可以表示为 $A_1A_2...A_n$。

对于任意两个矩阵 $A_i$ 和 $A_j$，它们可以相乘当且仅当矩阵 $A_i$ 的列数等于矩阵 $A_j$ 的行数，即 $p_{i} = p_{j-1}$。因此，将这 $n$ 个矩阵连乘起来的总乘法次数可以表示为：

$$M_{i,j}=\left\{\begin{array}{ll}{0} & {\text { if } i=j} \\ {\min _{i \leq k<j}\{M_{i, k}+M_{k+1, j}+p_{i-1} p_{k} p_{j}\}} & {\text { if } i<j}\end{array}\right.$$

其中，$M_{i,j}$ 表示将矩阵 $A_i$ 到 $A_j$ 这些矩阵相乘的最小乘法次数。

根据上述公式，可以采用自底向上的方式，先计算出 $M_{1,2}, M_{2,3},..., M_{n-1,n}$，再计算 $M_{1,3}, M_{2,4},..., M_{n-2,n}$，一直计算到 $M_{1,n}$，即可得到最小乘法次数。

动态规划求矩阵连乘问题的时间复杂度为 $O(n^3)$。