矩陣乘法鏈 (AP325 Q-6-18)

兩個矩陣 \(A\) 與 \(B\) 要相乘，必須滿足 \(A\) 的行數等於 \(B\) 的列數，若 \(A\) 是 \(p \times q\) 的矩陣，\(B\) 是 \(q \times r\) 的矩陣，則 \(A \times B\) 的結果是一個 \(p \times r\) 的矩陣，而需要的純量乘法數假設是 \(p \times q \times r\)。矩陣乘法滿足結合律，也就是說 \(A \times B \times C = (A \times B) \times C = A \times (B \times C)\)，可是不同順序所需要的純量乘法數不同。輸入 \(p[0], p[1], \ldots, p[n]\)，代表有 \(n\) 個矩陣相乘的乘法鏈，而它們的矩陣的大小依序分別是 \(p[0] \times p[1]\)、\(p[1] \times p[2]\)、\(\ldots\)、\(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 \times A_2) \times A_3\) 時，乘法數 \(3 \times 5 \times 4 + 3 \times 4 \times 2 = 84\)；若乘法順序為 \(A_1 \times (A_2 \times A_3)\) 時，乘法數 \(3 \times 5 \times 2 + 5 \times 4 \times 2 = 70\)。最少的純量乘法數為 \(70\)。

輸入格式

第一行是正整數 \(n\)。第二行有 \(n + 1\) 個正整數 \(p[0] \sim p[n]\)，數字間以空白隔開。

限制

• \(n \le 200\)。
• \(p[i] \le 200\)。

輸出格式

輸出最小的純量乘法數量。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

本題只要求 \(O(n^3)\) 的複雜度。

範例輸入 1

3
3 5 4 2

範例輸出 1

70

範例輸入 2

4
5 1 3 4 2

範例輸出 2

30

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 6 章 Q-6-18，第 200 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。