首页 > 试题广场 >

矩阵乘法计算量估算

[编程题]矩阵乘法计算量估算

矩阵乘法的运算量与矩阵乘法的顺序强相关。
例如：

A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵

计算A*B*C有两种顺序：((AB)C)或者(A(BC))，前者需要计算15000次乘法，后者只需要3500次。

编写程序计算不同的计算顺序需要进行的乘法次数。

数据范围：矩阵个数： $1\le n\le 15 \$ ，行列数： $1\le row_i,col_i\le 100\$ ，保证给出的字符串表示的计算顺序唯一。

进阶：时间复杂度： $O(n)\$ ，空间复杂度： $O(n)\$

输入多行，先输入要计算乘法的矩阵个数n，每个矩阵的行数，列数，总共2n的数，最后输入要计算的法则
计算的法则为一个字符串，仅由左右括号和大写字母（'A'~'Z'）组成，保证括号是匹配的且输入合法！

输出需要进行的乘法次数

示例1

输入

3
50 10
10 20
20 5
(A(BC))

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

字符串栈

难度：

0条回答 1987收藏 33428浏览

查看代码

扫一扫，把题目装进口袋