申論 4矩陣相乘是問題解決中常見的計算，但相乘順序對於計算效能有極大的影響。給定n 個矩陣，A, A, …, A，且任一矩陣A 大小為p ×p,p,...,p皆為正整數。A × A × … × A 實12nii−1i0n12n際計算過程可以是(…((A × A) × A) × … × A)、(A × (A × (…× (A × (A × A))…)))、或123n12n-2n-1n其他合理的順序，而因矩陣相乘順序不同，所需要的乘法運算次數可能也會不同。透過動態規劃（dynamic programming）、二維陣列的應用及遞迴程式，可以找到最少乘法運算次數的計算順序。方法如下：令m[i,j]為計算A × A × … × A 時所需最少乘法運算次數，ii+1jm[i,j]可以下列遞迴公式表示之：⎧min{m[i,k]+m[k+,1j]+ppp},ifi<jm[i,j]=⎨i−1kji≤k<j⎩,0ifi≥j㈠請說明A × A × … × A 相乘過後的矩陣大小為何？（3 分）12n㈡透過上述方法所找到的最少乘法運算次數，應為二維陣列m[i,j]中的那個元素，亦即i, j應分別為何？（3 分）㈢若n = 4 且p,p,p,p,p分別為3, 4, 5, 4, 2，請計算並填寫出二維陣列m[i,j]。（11 分）㈣承上小題㈢，請說明該四矩陣相乘，A × A × A × A，最少共需有幾次乘法運算。（3 分）