題目連結：
題目大意：
輸入有多筆測試資料，每筆佔兩列。測資第一列給定一正整數 N （N ≦ 1000），代表有 N 張卡片排成一排。接著的一列給定 N 個正整數（皆介於 1（含） ～ 100（含） 之間），代表這 N 張卡片的值。
對於剩下 > 2 張卡片的情況，可以從中挑選一張不是頭和尾的卡片（也就是只能選隊伍中間的），將該卡片移除並獲得等同其相鄰卡片（即在它的左右之卡片）之值乘積的獎金金額。然後重複此過程，直到只剩原卡片隊伍的頭與尾（因為這兩張一個缺了左邊、一個缺了右邊的卡片，所以乘積等同無意義）。
試問，最大可能的總獎金為何？
範例輸入：
4
3 5 10 9
5
5 10 7 8 4
5
5 10 7 8 6
範例輸出：
72
140
170
解題思維：
其實跟昨天的題目很像。
將卡片值之數列命名為 C0 、 C1 、 …… 、 CN-1 ，並定義二維陣列 Di, j （0 ≦ i ≦ j < N），代表 Ci ～ Cj 這 j - i + 1 張卡片之局面可以獲得的最大獎金金額。
可以看到其遞迴式：
當 i ＝ j 時， Di, j ＝ 0
當 i < j - 1 時，Di, j ＝ min(Di, k + Dk, j + Ci × Cj) ， 其中 i < k < j 。
而做法就跟昨天的題目如出一轍。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
