algorithm - 动态规划 - "maximize"矩阵链乘法

Question

我现在正在自己练习动态规划。对于经典问题“矩阵链乘法”，就是求标量乘法的最小数。即，

M[i,j] = 0 if i=j
       = Min(i<=k<j){M[i,k-1]+M[k,j]+Pi-1*Pj*Pk}
and its time complexity is O(n^3)

但我很好奇，如果我想找到标量乘法的“最大化”(而不是最小值)，它是否存在最优结构，是否有可能在多项式时间内求解？

Answer 1

与最小化应用完全相同的推理:

• 如果您将 a₁ ... a_i 相乘，则生成的矩阵维度不依赖于内部括号。

• 由此可见，如果 a₁ ... a_i ... a 的最优 - 即最昂贵 - 分区_n是将1到i和i + 1到的矩阵相乘>n，则由a₁ ... a_i 和a< 的最优解码成sub>i + 1 ... a_n

由于最优子结构仍然存在，您可以使用与最小化相同的算法(当然，将最优性标准从最小值更改为最大值)。