动态规划法求解矩阵连乘问题的方法

矩阵连乘问题，即给定n个矩阵Ai(Ai-1 * Ai，i=1,2,...,n)，对于所有的i和j，满足1<=i<=j<=n，询问Ai* Ai + 1 *...* Aj的最佳计算次序，即如何矩阵连乘使得乘法的次数最少。

矩阵连乘问题可以用动态规划法求解。动态规划作为一种算法方法，自20世纪50年代诞生以来，毫无疑问已经成为了计算机科学中最重要的算法之一，因为它可以针对很多的优化问题提供多项式算法。

在矩阵连乘问题中，我们用m[i][j]来表示连乘矩阵 Ai* Ai+1* … * Aj的最小计算次数，其中i和j满足1<=i<=j<=n。因此，我们需要在求解m[i][j]的同时，记录计算次数最少的分割点k位置。其中，分割点k是指将ma * mb连乘时的总计算次数为ma * mb * mc的分割点，分割点k在计算时是不固定的。

为了求解m[i][j]值，假设有两个相邻的矩阵Ai(Ai-1 * Ai)和Aj(Aj-1 * Aj)，其中Ai的维数为pi-1 * pi，Aj的维数为pj-1 * pj。这两个矩阵的成绩为（Ai-1 * Ai）*（Aj-1 * Aj），即（pi-1 * pi * pj-1）* （pj-1 * pj）。考虑到计算次序的不同将分割点分为了左边与右边的两部分，从而导致了Ai * Ai+1* …* Aj的计算。因此，对于任何分割点k，我们都需要计算Ai * Ai+1* …* Ak和Ak+1* …* Aj的两部分，在左侧矩阵的最佳计算次序m[i][k]和右侧矩阵的最佳计算次序m[k+1][j]基础上计算代价，并将其相加，以覆盖所有可能的分割点k，从而得到Ai* Ai+1* …* Aj的最佳计算次序m[i][j]。

在动态规划求解的过程中，我们还需要记录当前的最佳分割点，以便在表格中回溯来找出最佳的分割点。我们通过记录整个m表格，m[i][j]存放计算矩阵Ai* Ai+1* …* Aj所需的最小乘法次数，s[i][j]保存最小乘法次数的分割点k的值。以及3个辅助过程（Matrix-Chain-Order算法、print-OPtimal-Parens算法、Lookup-Chain算法）实现基于动态规划的最佳分割点k查找。

综上所述，矩阵连乘问题使用动态规划算法求解时，可以通过三种基础算法（Matrix-Chain-Order、print-OPtimal-Parens、Lookup-Chain）来维护所需要的矩阵。这样，我们可以基于这些算法，在时间复杂度为O（n^3）的情况下，找到最小的计算次序，这是任何暴力算法都做不到的，也是完全利用重复计算缓存转移求解答案的方法。