行列 $A_1$（2×10）、$A_2$（10×5）、$A_3$（5×20）の積 $A_1{A}_2{A}_3$ を計算する。p×q 行列と q×r 行列の積に必要なスカラーの乗算回数を pqr とするとき、計算順序を最適に選んだ場合の乗算回数の合計はいくつか。

解説

正解は「300」です。行列の積は結合法則が成り立つので、計算順序を選べます。$(A_1{A}_2)A_3$ では、まず $2\times 10\times 5=100$ 回で2×5行列を作り、次に $2\times 5\times 20=200$ 回で、合計300回です。$A_1(A_2{A}_3)$ では、$10\times 5\times 20=1000$ 回で10×20行列を作り、次に $2\times 10\times 20=400$ 回で、合計1400回です。「1400」は計算順序が不利な方の回数です。「1000」は $A_2{A}_3$ の計算だけを数えた値です。「200」は $(A_1{A}_2)A_3$ の2回目の積だけを数えた値です。行列の数が増えると、部分列の最小コストを表に記録する動的計画法で最適な順序を求めます。