兩個矩陣 $A$ 與 $B$ 要相乘，必須滿足 $A$ 的行數等於 $B$ 的列數，若 $A$ 是 $p \times q$ 的矩陣，$B$ 是 $q \times r$ 的矩陣，則 $A * B$ 的結果是一個 $p \times r$的矩陣，而需要的純量乘法數假設是 $p \times q \times r$。 矩陣乘法滿足結合律，也就是說  $A*B*C = (A*B)*C = A*(B*C)$，可是不同順序所需要的純量乘法數不同。

輸入 $p[0], p[1], \dots , p[n]$，代表有 $n$ 個矩陣相乘的乘法鏈，而它們的矩陣的大小依序分別是 $p[0] \times p[1]$、$p[1] \times p[2]$、…、 $p[n-1] \times p[n]$，請找出最好的相乘順序使得使用的純量乘法數的總和最少。

舉例來說，$n=3$，矩陣大小為，$A1: 3 \times 5$、$A2: 5 \times 4$、$A3: 4 \times 2$。
乘法順序為 $(A1 *A2) * A3$ 時，乘法數 3 * 5 * 4 + 3 * 4 * 2 = 84；
若乘法順序為 $A1 *(A2 * A3)$ 時，乘法數 3 * 5 * 2 + 5 * 4 * 2 = 70。
最少的純量乘法數為 70。