动态规划处理矩阵连乘问题的方法

在动态规划算法框架内，在局部最优未必能保证全局最优的情况下，在每个时间段内的决策会影响后续进程。当我们把一个问题划分成多个阶段时，在各子问题之间需记录状态信息，并为后续处理提供依据。通常用于解决子问题存在重叠的情况。下面是一个矩阵连乘的问题

问题：n个矩阵连乘问题

描述：矩阵连乘遵循结合律，在进行n个矩阵相乘运算时，请问哪种结合顺序能够使得整个过程中的乘法操作次数最少？其中AB表示两个矩阵A和B的乘积。

数量化：记 Mi * Mi+1 … * Mj 的乘法次数记为Mi,j，矩阵大小为：

M1=r1 *r2，M2 =r2 *r3, Mi =ri * ri+1。

由此可见，在i=j的情况下（即连乘式子中仅包含一个矩阵），我们能够明确得知此时Mi,j=0；而当j等于i加一时，则该值等于ri×ri+1×ri+2。在由n个矩阵组成的连乘式子M₁×M₂×…×Mₙ中，则可以直接推断出所有相邻两矩阵相乘所需的运算次数。此结论暂且记录下来

接着，在j大于i的情况下, 我们可以根据结合律将其分成两个连续的乘积部分.

(Mi ⋯ Mk) ⋅ (M_{k+1} ⋯ M_j)，值得注意的是这里的k值并非仅限于单一数值而是可以在i到j范围内取不同值从而生成如下的两种形式：

Mi * (Mi+1 *… * Mj ) k = i

(Mi * Mi+1