主題
題目連結：
題目大意：
給定一正整數 Ｎ （Ｎ ≦ １０），代表有 Ｎ 個矩陣要相乘。接著有 Ｎ 列輸入，每列給定兩正整數。這 Ｎ 列分別代表第一個矩陣、第二個矩陣……（以下稱 Ａ１ 、 Ａ２ ……）有幾列（Rows）幾行（Columns）。
這 Ｎ 個矩陣相乘的結果即為 Ａ１ × Ａ２ × …… × ＡＮ ，但是有可能因為運算順序不同而導致相乘時的乘法運算次數不同。例 Ａ１ ＝ １ × ５ 、 Ａ２ ＝ ５ × １０ 、 Ａ３ ＝ １０ × ５（列數 × 行數），若先算 Ａ１ × Ａ２ 再乘以 Ａ３ ，則用了 １００ 次的乘法運算；若是先求 Ａ２ × Ａ３，左邊再乘以 Ａ１ ，則用了 ２７５ 次乘法。
因此，本題目標是給定 Ｎ 個矩陣的行列值，求怎樣的運算順序可以使得運算次數最小化。將運算順序用括號表示出來。輸出格式參見範例輸出。
範例輸入：
3
1 5
5 20
20 1
3
5 10
10 20
20 35
6
30 35
35 15
15 5
5 10
10 20
20 25
0
範例輸出：
Case 1: (A1 x (A2 x A3))
Case 2: ((A1 x A2) x A3)
Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))
解題思維：
定義兩個二維陣列，Ｄｉ,ｊ 以及 Ｐｉ,ｊ ，分別代表第 ｉ ～ ｊ 個矩陣相乘所需最小的乘法運算次數和從哪兩個矩陣中間分割（先各自算左右兩邊，再合併）可以使得 ｉ ～ ｊ 的相乘運算次數最小。
則可得知：
其中 Ｄｉ,ｋ 之 ｋ 代表窮舉 ｉ ～ ｊ 從何者分割（即 ｉ ≦ ｋ ≦ ｊ）、Ｒｉ 代表第 ｉ 個矩陣的列數、 Ｃｋ 代表第 ｋ 個矩陣的行數。
因此，
我們可以像這樣子一步一步推出 Ｄ１, Ｎ 的值。先設定 Ｄ１, １ 、 Ｄ２, ２ …… ＤＮ, Ｎ 為零。再對於每個 ｉ ～ ｉ ＋ １ 用上面遞迴式窮舉分割點 ｋ 的方式求出 Ｄｉ, ｉ＋１ 。再用類似的方法窮舉 ｉ ～ ｉ ＋ ２ 的分割，得出 Ｄｉ, ｉ＋２ ……以此類推。最後便可得出所求的 Ｄ１, Ｎ 。
以上是單純求最小的運算次數，而要求最佳的分割也可以用上面的方法。只要在窮舉分割的時候，只要窮舉出的 ｋ 值造成比當前的解（當前的 Ｄｉ, ｊ）更小的次數，則Ｐｉ, ｊ 便等於 ｋ 。
最後要輸出最佳的運算順序的括號時，便是先輸出一個「(」，然後遞迴分割點（Ｐｉ, ｊ）的左半邊（ｉ～ Ｐｉ, ｊ）。再輸出一個「x」，再遞迴右半邊（Ｐｉ, ｊ ～ ｊ），最後輸出一個「)」。而當遞迴的時候，若 ｉ ＝ ｊ 時，則輸出「Ai」（此時要輸出ｉ的值，而不是「ｉ」），並回到上一層的遞迴堆疊。
然而，原題雖說輸出任意一組可行解就好（可能有多種解）。但是因為本題沒有特別判斷，因此要照其規則來找出題目要的可行解——當有一個陣列可分在左右兩邊而不影響結果時，就把它歸類在左半邊。因此窮舉 ｉ 的時候，要由大至小窮舉。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
