Question

动态规划之矩阵连乘问题

Answer 1

矩阵连乘问题：设M1 M2 M3 ... Mn 为n个矩阵序列，其中Mi为 r[i] * r[i+1]阶矩阵，i=1,2,3 ... n。这个矩阵链的输入是向量 R=<r[0],r[1],[2]...r[n]>,因为矩阵运算满足结合律，所以运算结果与计算顺序无关，但是不同运算顺序，会造成运算时的乘法次数的不同。
求以哪种乘法次序运算，使得基本运算的总次数最少

举个栗子:
M1[5 * 20] * M2[20 * 50] * M3[50 * 1] * M4[1 100]

可能的运算次序有多种,如:
1. ((M1[5 * 20] * M2[20 * 50]) * M3[50 * 1]) * M4[1 100]
2. M1[5 * 20] * (M2[20 * 50] * (M3[50 * 1] * M4[1 100]))
3. (M1[5 * 20] * (M2[20 * 50] * M3[50 * 1])) * M4[1 100]