给定一个矩阵序列<A1,A2,…,An>，计算乘积A1A2…An。要求找出一个加全部括号的方式，使得标量乘法的次数最小。
加全部括号：
性质1，A1A2…An相乘，必须满足前一个矩阵的列数等于后一个矩阵的行数。
证明：假设Ai的列数为pi，i=1,…,n。下面我们来看各矩阵的行数。
当n=2时，根据矩阵乘法的定义可知，A1的列数等于A2的行数。因此，A2的行数等于p1。
当n=3时，因为A1A2相乘得到的新矩阵的列数为p2，而A1A2和A3可以相乘，因此A3的行数为p2。 依次类推，Ai(i≥2)的行数为pi-1，得证。
性质2，序列中的任何n个相邻矩阵都可以直接相乘，n≥2。
证明：
根据性质1可知，任意两个相邻矩阵都可以相乘，即n=2时，满足上述性质。
n=3时，假设我们选择任意相邻矩阵Ai-1AiAi+1，根据矩阵性质，Ai-1Ai得到的新矩阵为pi-2×pi，而Ai+1为pi×pi+1，因此Ai-1Ai得到的矩阵可以与Ai+1相乘，即Ai-1AiAi+1可以相乘。由于这三个矩阵是任意选择的，因此，n=3时，满足上述性质。
依次类推，对于任意n>=2，均满足上述性质。得证。
加全部括号具体步骤如下：
- 步骤一：选取相邻的两个矩阵，加括号；
- 步骤二：将步骤一中的括号看做一个新的矩阵，放回原先位置，得到一个新的序列；
- 步骤三：如果新序列中矩阵个数等于1，则结束，否则，返回步骤一。
也可以按照下面步骤进行加括号：
- 步骤一：如果当前序列只有一个矩阵，则不需加括号，否则将整个序列最外层加一个括号，使其成为一个新序列；
- 步骤二：检查序列里面是否有两个以上矩阵；
- 步骤三：如果是，则在这些矩阵中找一个分界点，将其分为两个新序列，对这两个新序列分别从步骤一开始重复执行上述步骤。
对于任意两个矩阵AiAi+1相乘，其乘法次数为pi-1pi pi+1，不同的加全部括号，所需要的乘法次数可能相差很大。
假设现在有三个矩阵A1A2A3相乘，维数分别为：10×100，100×5，5×50。
1、如果我们采用如下方式加全部括号：
(（A1A2）A3)
则
首先计算（A1A2），乘法次数为p0p1p2，得到新矩阵的维数为p0×p2
计算(（A1A2）A3)，乘法次数为p0p2p3，
总的计算次数为p0p1p2+ p0p2p3=10×100×5+10×5×50=7500
2、如果我们采用如下方式加全部括号：
(A1（A2 A3）)
则
首先计算（A2 A3），乘法次数为p1 p2 p3，得到新矩阵的维数为p1× p3
计算(A1（A2 A3）)，乘法次数为p0p1 p3，
总的计算次数为p1 p2 p3+ p0p1 p3=100×5×50+10×100×50=75000
第二种方式需要的次数是第一种的10倍！