动态规划矩阵连乘的复杂度计算

矩阵连乘问题可以使用动态规划来解决。假设有n个矩阵{A1, A2, ..., An}，其中Ai的维度为pi-1×pi（1≤i≤n），要求对它们进行连乘，即(A1×A2×...×An)。

定义m[i,j]表示Ai×Ai+1×...×Aj的最小乘法次数，那么有以下递推式：

m[i,j] = 0, (i=j)
m[i,j] = min{m[i,k]+m[k+1,j]+pi-1×pk×pj}, (i≤k<j)

其中，i和j表示矩阵序列的起点和终点，k表示断点，pi表示矩阵Ai的行数，pj表示矩阵Aj的列数，pk表示矩阵Ak的列数。

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