Q-6-18. 矩陣乘法鏈
矩陣乘法必須滿足 A 的行數等於 B 的列數,若 A 是 \(p \times q\) 的矩陣,B 是 \(q \times r\) 的矩陣,則 \(A \times B\) 的結果是一個 \(p \times r\) 的矩陣,而需要的純量乘法數為 \(p \cdot q \cdot r\)。
矩陣乘法滿足結合律,也就是說 \(A \times B \times C = (A \times B) \times C = A \times (B \times C)\),可是不同順序所需要的純量乘法數會不同。
輸入 \(p[0], p[1], \dots, p[n]\),代表有 \(n\) 個矩陣相乘的乘法鏈,而它們的矩陣大小依序為 \(p[0] \times p[1], p[1] \times p[2], \dots, 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 \cdot 5 \cdot 4 + 3 \cdot 4 \cdot 2 = 84\)
乘法順序 \(A_1 \times (A_2 \times A_3)\):
- 乘法數:\(3 \cdot 5 \cdot 2 + 5 \cdot 4 \cdot 2 = 70\)
最少的純量乘法數為 \(70\)。
輸入格式
第一行是正整數 n。 第二行有 n+1 個正整數, p[0] ~ p[n],數字間以空白隔開。 n <= 200,p[i] <= 200
輸出格式
最小的純量乘法數量。
範例輸入 1
3
3 5 4 2
範例輸出 1
70
範例輸入 2
4
5 1 3 4 2
範例輸出 2
30
留言