矩阵链乘法问题的目标是找到最有效的方法来乘以给定的 n 个矩阵 M1,M2,M3,...,Mn。 编写一个程序，读取 Mi 的维度，并找到最小标量乘法以计算最大链链乘法 M1M2...Mn。 输入 在第一行中，给出了一个整数 n。 在接下来的 n 行中，矩阵 Mi (i=1...n) 的维度由两个整数 r 和 c 给出，分别表示 Mi 的行数和列数。 输出 在一行中打印最小数量的标量乘法。 约束 1≤n≤100 1≤r,c≤100

这是一个经典的动态规划问题。我们可以定义一个二维数组 dp，其中 dp[i][j] 表示从矩阵 i 到 j 的最小标量乘积。根据矩阵链乘法的性质，我们可以得到以下递推关系：

dp[i][j] = min(dp[i][k] + dp[k+1][j] + r[i]*c[k]*c[j])

其中，k 的范围应该是 i <= k < j，r[i] 表示矩阵 i 的行数，c[k] 表示矩阵 k 的列数，c[j] 表示矩阵 j 的列数。这个递推关系的意思是，我们将矩阵链拆分成两个部分，分别是 i 到 k 和 k+1 到 j，然后计算它们的最小标量乘积，再加上它们相乘的代价 r[i]*c[k]*c[j]，最后取所有可能的 k 中的最小值即可。

根据这个递推关系，我们可以写出以下代码：