兩個矩陣 A 與 B 要相乘，必須滿足 A 的行數等於 B 的列數，若 A 是 p×q 的矩陣，B 是q×r的矩陣，則A×B的結果是一個p×r的矩陣，而需要的純量乘法數假設是p×q×r。 矩陣乘法滿足結合律，也就是說 A×B×C = (A×B)×C = A×(B×C)，可是不同順序所 需要的純量乘法數不同。輸入 p[0], p[1], …, p[n]，代表有 n 個矩陣相乘的乘 法鏈，而它們的矩陣的大小依序分別是 p[0]×p[1]、p[1]×p[2]、…、 p[n-1]×p[n]，請找出最好的相乘順序使得使用的純量乘法數的總和最少。 舉例來說，n=3，矩陣大小為，A1: 3 × 5, A2: 5 × 4, A3: 4× 2 乘法順序為(A1 × A2) × A3 時，乘法數 3 * 5 * 4 + 3 * 4 * 2 = 84；若乘 法順序為 A1 ×(A2 ×A3)時，乘法數 3 * 5 * 2 + 5 * 4 * 2 = 70。最少的 純量乘法數為 70。
第一行是正整數 n。第二行有 n+1 個正整數， p[0] ~ p[n]，數字間以 空白隔開。n≤ 200，p[i] ≤ 200。
最小的純量乘法數量。
3 3 5 4 2
70
4 5 1 3 4 2
30
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||