动态规划实现矩阵连乘问题算法思想

动态规划是求解矩阵连乘问题的经典算法之一。矩阵连乘问题是一个典型的最优化问题，其目标是找到一种矩阵乘法的顺序，使得计算矩阵连乘所需的标量乘法次数最少。

动态规划算法的基本思想是将原问题划分成若干个子问题进行求解，并将子问题的解缓存起来，避免重复计算。在矩阵连乘问题中，我们可以将原问题划分成多个子问题，例如将矩阵序列划分为两个子序列，然后分别对这两个子序列进行矩阵连乘，最后再将两个结果合并。

具体实现时，我们可以使用一个二维数组来记录每一个子问题的最优解。设M(i,j)表示计算从第i个矩阵到第j个矩阵所需的最小标量乘法次数，则可以得到以下递推公式：

M(i,j)=min{M(i,k)+M(k+1,j)+p(i-1)*p(k)*p(j)}, i<=k<j

其中p为矩阵序列的维数数组。这个递推公式的意义是：在计算第i个矩阵到第j个矩阵的乘积时，先将这些矩阵划分成两部分：从i到k和从k+1到j，然后计算这两部分的最小标量乘积次数，再加上这两部分的乘积所需的次数p(i-1)*p(k)*p(j)。

最终，M(1,n)即为所求的最小标量乘法次数。