用动态规划策略求矩阵链相乘的最小乘法次数及乘法方式

矩阵链相乘问题是指给定n个矩阵，它们的维度分别为A1A2, A2A3, ..., An-1An，现在要将它们相乘，求出最少的乘法次数以及相乘的顺序。

动态规划是解决矩阵链相乘问题的有效方法。我们可以定义一个二维数组dp，其中dp[i][j]表示从第i个矩阵到第j个矩阵相乘的最小乘法次数。因此，最终答案就是dp[1][n]。

我们可以根据以下递推式来计算dp[i][j]：

dp[i][j] = min{dp[i][k] + dp[k+1][j] + Ai-1AkAj}，其中i ≤ k < j，Ai-1Ak和AkAj分别表示第i-1个矩阵和第j个矩阵的维度。

在计算dp数组时，我们需要先初始化所有的dp[i][i]为0，然后按照矩阵链长度从小到大的顺序依次计算dp[i][j]。

最后，我们可以通过记录每次的最小值所对应的k值来确定乘法的顺序。具体来说，我们可以维护一个二维数组s，其中s[i][j]表示从第i个矩阵到第j个矩阵相乘时，最后一次乘法所在的位置k。在计算dp[i][j]时，如果dp[i][k] + dp[k+1][j] + Ai-1AkAj的值最小，则更新s[i][j]为k。

最后，我们可以通过递归地遍历s数组来输出最终的乘法顺序。具体来说，我们可以定义一个函数printMultiplication，它的输入参数为s数组、第一个矩阵的下标i和最后一个矩阵的下标j。在函数内部，如果i=j，则直接输出矩阵Ai；否则，先递归输出从i到s[i][j]相乘的结果，再递归输出从s[i][j]+1到j相乘的结果，最后将它们相乘即可。

这样，我们就可以通过动态规划来求解矩阵链相乘的最小乘法次数及乘法方式了。