【输入形式】 第1行为一个正整数n，表示n个矩阵相乘，n≤100。 第2行为n+1个整数p0p1……pn，其中pi-1pi为矩阵Ai的行数和列数。 【输出形式】 一个整数，为最小乘法次数

以下是Python代码实现：

n = int(input())
p = list(map(int, input().split()))

# 初始化dp数组
dp = [[0] * (n+1) for _ in range(n+1)]

# 动态规划求解
for length in range(2, n+1):
    for i in range(1, n-length+2):
        j = i + length - 1
        dp[i][j] = float('inf')
        for k in range(i, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j])

# 输出结果
print(dp[1][n])

时间复杂度为O(n^3)，可以通过本题。

相关问题

输入一个正整数n（1≤n≤10），输出n×n的简易乘法表。当n=3时，3×3的简易乘法表如下：

### 回答1：
可以使用以下 Python 代码实现输出n×n的简易乘法表:

n = int(input("请输入一个正整数："))
for i in range(1,n+1):
    for j in range(1,n+1):
        print(i*j, end="\t")
    print()

这段代码中，首先使用input()函数接收用户输入的正整数n。然后使用两个for循环，第一个循环控制行数，第二个循环控制列数，在循环内部使用print()函数输出乘积，end="\t"表示在输出完一个数之后不换行，而是在同一行输出下一个数。最后在外层循环中使用print()函数换行输出下一行的乘积。

当 n = 3 时的输出如下：

1	2	3	
2	4	6	
3	6	9	

### 回答2：
简易乘法表是一个常见的数学学习工具，可以帮助孩子们更好地了解乘法的概念，掌握乘法的规律。给定一个正整数n（1≤n≤10），输出n×n的简易乘法表。

简易乘法表的基本原理很简单，就是利用乘法的规律，将n个数依次与1~n相乘，得到n×n的乘法表。

以n=3为例，3×3的简易乘法表如下：

| 1 | 2 | 3 |
|---|---|---|
| 2 | 4 | 6 |
| 3 | 6 | 9 |

从上表可以看出，这是一个由n行n列组成的表格，每个表格中的数都是两个数的乘积。其中第一行和第一列是从1开始依次递增的自然数，而从第二行第二列开始，每个表格中的数都是前面一行、一列的两个数相乘所得。

因此，要生成一个n×n的简易乘法表，只需要在代码中使用两个循环，分别循环1~n，将每个数依次与1~n相乘即可。代码如下：

n = int(input("请输入一个正整数n（1≤n≤10）："))
# 按行输出简易乘法表
for i in range(1, n+1):
    # 按列输出每个数的乘积
    for j in range(1, n+1):
        # 输出两个数的乘积，并在后面加一个制表符，使其对齐
        print(i*j, end='\t')
    # 换行
    print()

运行以上代码，就可以得到输入n后对应的n×n简易乘法表了。

### 回答3：
简易乘法表是小学数学里常见的一种学习工具，它通过将自然数依次相乘，生成的一张表格，来帮助学生加深对乘法运算的理解。对于本题所述的简易乘法表，我们需要输入一个正整数n（1≤n≤10），并输出n×n的表格。

在计算机程序中，我们可以通过两个嵌套的for循环，将相乘的结果输出到矩阵中。具体来说，外层循环i遍历1到n的范围，内层循环j遍历1到n的范围。当i等于1时，我们输出表头，即“×1 2 3 ... n”这一行；当j等于1时，我们输出这一行的第一个元素i，然后内层循环从2开始遍历，并将i*j输出到矩阵中；当内层循环j遍历完毕后，我们需要换行输出下一行。

当n=3时，我们可以按照以上流程，输出3×3的简易乘法表。具体实现如下：

int n = 3; // n为输入的正整数
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == 1) { // 输出表头
cout << "x" << j << " ";
} else if (j == 1) { // 输出第一个元素
cout << i * j << " ";
} else { // 输出乘积
cout << i * j << " ";
}
}
cout << endl; // 换行
}

以上代码中，我们首先定义了n为3，然后通过两个嵌套的for循环，将表格输出到控制台中。运行结果如下：

x1 x2 x3
1 2 3
2 4 6
3 6 9

至此，我们成功地实现了一个简易乘法表的生成程序。在实际应用中，我们可以将其扩展到更大的整数范围，并将其输出到文件、数据库等数据源中，以供其他程序调用。

•问题描述 数学上规定，两个矩阵相乘A×B必须满足的条件是A的列数等于B的行数，并且矩阵乘法没有交换律。对于n个矩阵连乘A1×A2×……×An，第i个矩阵的列数必须等于第i+1个矩阵的列数。 在满足该条件的前提下，不同的计算次序可能导致矩阵元素乘法(对应于计算机辅助计算时CPU执行乘法指令的次数)的次数不同，为此，需要在各种可能的计算次序中找出其中元素乘法最少的那一种。 •输入格式 输入的第1行是1个整数，记作n，表示一共有多少个矩阵。从第2行开始每行是用逗号分隔的两个正整数，表示一个矩阵的行数和列数。 •输出格式 输出有两行，第1行是n-1个整数，是1到n-1的一种排列，用空格分隔，表示乘法的次序，即依次执行第几个乘号的矩阵乘法(n个矩阵连乘当然是n-1个乘号)。第2行是1个正整数，表示在上述计算次序之下共需要多少次元素乘法。

这是一道典型的动态规划问题，可以使用动态规划求解。

设 $f(i,j)$ 表示从第 $i$ 个矩阵到第 $j$ 个矩阵连乘的最小次数，$m(i,j)$ 表示从第 $i$ 个矩阵到第 $j$ 个矩阵的乘积矩阵的行数。

则有状态转移方程：

$$f(i,j)=\begin{cases}0 & i=j\\ \min\limits_{i\le k<j}\{f(i,k)+f(k+1,j)+m(i,k)m(k+1,j)\} & i<j\end{cases}$$

初始条件为 $f(i,i)=0$，最终答案为 $f(1,n)$。

具体实现时，可以使用二维数组 $dp[i][j]$ 来保存 $f(i,j)$ 的值，使用二维数组 $m[i][j]$ 来保存 $m(i,j)$ 的值，使用二维数组 $s[i][j]$ 来保存最优计算次序下从第 $i$ 个矩阵到第 $j$ 个矩阵的分界点 $k$，即 $f(i,j)=f(i,k)+f(k+1,j)+m(i,k)m(k+1,j)$ 中取到最小值时的 $k$。

最后，根据 $s$ 数组可以递归地输出最优计算次序。

时间复杂度为 $O(n^3)$。

以下是Python实现：