兩個矩陣 $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$，矩陣大小為，$A_1: 3 \times 5$、$A_2: 5 \times 4$、$A_3: 4 \times 2$。
乘法順序為 $(A_1 *A_2) * A_3$ 時，乘法數 3 * 5 * 4 + 3 * 4 * 2 = 84；
若乘法順序為 $A_1 *(A_2 * A3)$ 時，乘法數 3 * 5 * 2 + 5 * 4 * 2 = 70。
最少的純量乘法數為 70。