动态规划--矩阵连乘问题
前面步骤省略
代码解析
伪代码
2~3行：将m[i,i]值全赋0
4行：l为每次所分的矩阵链的长度（2到n）
5行：每个矩阵链的起始位置为i(1<=i<=n-l+1)
6行：每个矩阵链的起始位置为j(j==i+l-1)
7行：先将m[i,j]的值赋为极限大
8行：在第四行遍历中所取得矩阵链中找到一个断裂点k（i<=k<=j-1），使得在此处断开时矩阵计算量最小，从k=i开始遍历，依次尝试计算并记录计算量
9行：记算在当前位置k断裂时所需的计算量 （pk是矩阵k的列数）
10行：如果当前计算量最小，
11行：就将当前计算量q写入到m表的[i,j]位置上（矩阵链(i,j)计算所需的最小计算量），并将断裂位置k写入s表的[i,j]处（即矩阵链(i,j)在k断开进行计算所需的计算量最小）
12行：返回结果
具体实现
时间复杂度
计算量主要取决于算法中的三重循环。循环体内的计算量为O(1)，三重循环的总循环次数为O(n3)，因此计算时间的上界为O(n3)。算法占用空间为O(n2)