矩阵连乘动态规划算法

矩阵连乘动态规划算法是一种用于确定矩阵连乘积计算次序的算法，使得依此次序计算矩阵连乘积需要的相乘次数最少。该算法的核心思想是将原问题分解为若干个子问题，并且记录已计算子问题的解，避免重复计算。具体来说，该算法通过构建一个n*n的二维数组m，其中m[i][j]表示Ai到Aj的矩阵连乘积所需的最少乘法次数，同时构建一个n*n的二维数组s，其中s[i][j]表示Ai到Aj的矩阵连乘积所需的最优计算次序中，第一个加括号的位置k。然后，通过枚举所有可能的切分策略，计算m[i][j]和s[i][j]的值，最终得到矩阵连乘积的最少乘法次数和最优计算次序。该算法的时间复杂度为O(n^3)。