矩阵链乘积

矩阵链乘积（或矩阵链排序问题，MCOP）是一个可以使用动态编程解决的优化问题。 给定一系列矩阵，目标是找到最有效的方法来乘以这些矩阵。 问题实际上不是执行乘法，而只是决定所涉及的矩阵乘法的顺序。

动态编程算法首先，让我们假设我们真正想要知道的是最小成本或乘以矩阵所需的最小算术运算数。如果我们只乘以两个矩阵，那么只有一种方法可以将它们相乘，因此最低成本就是这样做的成本。通常，我们可以使用以下递归算法找到最低成本：

1、采用矩阵序列并将其分成两个子序列。

2、找出乘以每个子序列的最低成本。

3、将这些成本加在一起，并增加两个结果矩阵相乘的成本。

4、对可以拆分矩阵序列的每个可能位置执行此操作，并对所有这些位置进行最小化。

例如，如果我们有四个矩阵ABCD，我们计算找到每个（A）（BCD），（AB）（CD）和（ABC）（D）所需的成本，进行递归调用以找到最小成本计算ABC，AB，CD和BCD。然后我们选择最好的一个。更好的是，这不仅产生了最低成本，而且还展示了进行乘法的最佳方式：将其分组为产生最低总成本的方式，并对每个因子进行相同的处理。

但是，如果我们实现这个算法，我们会发现它和尝试所有排列的天真方式一样慢！什么地方出了错？答案是我们正在做很多冗余的工作。例如，上面我们进行了递归调用，以找到计算ABC和AB的最佳成本。但是，找到计算ABC的最佳成本也需要找到AB的最佳成本。随着递归越来越深，越来越多的这种不必要的重复发生。

一个简单的解决方案叫做memoization：每当我们计算出乘以特定子序列所需的最低成本时，我们就会保存它。如果我们被要求再次计算它，我们只是给出已保存的答案，而不是重新计算它。由于存在大约n2 / 2个不同的子序列，其中n是矩阵的数量，因此执行此操作所需的空间是合理的。可以证明，这个简单的技巧将运行时从O（2n）降低到O（n3），这对于实际应用来说足够有效。这是自上而下的动态编程。

下面的自下而上方法使用已计算的较小子序列的成本，计算每个2≤k≤n的所有子序列k的最小成本。它具有相同的渐近运行时，不需要递归。

伪代码：

// Matrix A[i] has dimension dims[i-1] x dims[i] for i = 1..nMatrixChainOrder(int dims[]){ // length[dims] = n + 1 n = dims.length - 1; // m[i,j] = Minimum number of scalar multiplications (i.e., cost) // needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j] // The cost is zero when multiplying one matrix for (i = 1; i