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