申論題

四、矩陣相乘是問題解決中常見的計算，但相乘順序對於計算效能有極大的影響。給定 n 個矩陣， A₁, A₂, …, A_n，且任一矩陣 A_i 大小為皆為正整數。A₁ × A₂ × … × A_n 實際計算過程可以是(…((A₁ × A₂) × A₃) × … × A_n)、(A₁ × (A₂ × (…× (A_n-2 × (A_n-1 × A_n))…)))、或 其他合理的順序，而因矩陣相乘順序不同，所需要的乘法運算次數可能也會不同。透過動 態規劃（dynamic programming）、二維陣列的應用及遞迴程式，可以找到最少乘法運算次 數的計算順序。方法如下：令m[i, j]為計算 A_i × A_i+1 × … × A_j 時所需最少乘法運算次數， m[i, j]可以下列遞迴公式表示之： 

⑵透過上述方法所找到的最少乘法運算次數，應為二維陣列m[i, j]中的那個元素，亦即 i, j 應分別為何？（3 分）