問題描述
在一條直線上有n堆石子，每堆有一定的數量，每次可以將兩堆相鄰的石子合併，合併後放在兩堆的中間位置，合併的費用為兩堆石子的總數。求把所有石子合併成一堆的最小花費。
輸入格式
輸入第一行包含一個整數n，表示石子的堆數。
接下來一行，包含n個整數，按順序給出每堆石子的大小 。
輸出格式
輸出一個整數，表示合併的最小花費。
樣例輸入
5
1 2 3 4 5
樣例輸出
33 //3 6 9 15=33
以下為解題經歷：
第一反應，選擇用貪心的思想去解題，因為題中提到只能合併相鄰的石子，所以作一些改變，每次選擇最小的石子堆，比較其左右兩側的石子，選擇與較小的那個合併。
A[0..len] 取 Min(A) 將A[i] 與 Min(A[i 1],A[i-1]) 合併
其實此處，帶著一些僥倖心理，隱隱覺得不會正確，因為在兩兩合併的過程中，上一次的合併結果會對下一次的合併造成影響，每一次並非都獨立無關。
假如5堆石子，分別為7，6，5，7，100
•按照貪心，合併的過程如下：
7 6 5 7 100
7 11. 7 100
18. 7 100
25. 100
總得分＝11＋18＋25 125＝179
•另一種合併方案
7 6 5 7 100
13. 5 7 100
13 12. 100
25. 100
總得分＝13＋12＋25 125＝175
————————————————————————————————————
第二次解題，由於牽扯到不同情況下的不同解，第二反應是符合動態規劃的思想，利用一次次的合併過程去更新所得的結果，以便下一次合併使用。
首先，列出石子 進行觀察。A[i]為該堆中的石子個數
1.□ 2.□□ 3.□□□ 4.□□□□ 5.□□□□□
1.若石子有1堆，則無需合併，花費為0
2.若石子有2堆，則合併二者，花費為A[0] A[1]
3.若石子有3堆，則有2種情況，①先合併A[0]、A[1]再與A[2]合併 ②先合併A[1]、A[2]再與A[0]合併
4.若石子有4堆，則有3種情況，……………
總之，在n堆中，有n-1種情況，而最後一次合併總是以某兩堆合成一堆為結果。
即可將n堆劃分成A[0…k] 與 A[k 1…n-1]合併，
而A[0…k] 與 A[k 1…n-1]已是最優花費，由各自向下分解所得。
（遞迴思想，但由於此次是二維的，即符合動態規劃）
————————————————————————————————————
假設有5堆石子，則A[0…k] 與 A[k 1…n-1]的長度堆數可能為 1、4 2、3 3、2 4、1
只要其各自已為最優花費。
以上為遞推向下的邏輯，在動態規劃是由下而上，即5堆石子 需要長度為 2 3 4 的石子最優花費
如圖。
然後開始分析演算法過程，首先，最外層迴圈 控制石子堆長度（len=2 to n）,因為只有1堆時無需下續步驟
接著第二層迴圈，確定石子堆的起始堆號（i=0 to n-len）即為圖中的下劃線個數。
繼續分析，發現還需要一層迴圈控制更新 A[0…k] 與 A[k 1…n-1]的花費price (k=i to j-1)
確定無遺漏後，開始編寫程式碼過程，如下。
（注意，花費是每兩兩合併完的石子數依次相加，所以最後一次合併為合併堆數的總石子量）
——————————————————————————————————————————————、
由sum[i][j]表示第i堆石子到第j堆石子全部合併的總石子量。dp[i][j]為第i堆石子到第j堆合併的花費（隨著動態規劃的進行，會越來越越接近最優花費）dp[i][i]=0 （本身無需合併，不需花費）
即若僅兩堆石子合併 則dp[i][j]=dp[i][i] dp[j][j] sum[i][j] = 0 0 sum[i][j]
以下用一維sum[n]進行儲存，sum[i][j]=sum[j]-sum[i-1] (i!=0), sum[i][j]=sum[j] (i==0)
——————————————————————————————————————————————
完整程式碼如下：(時間限制：2.0s 記憶體限制：256.0MB 情況下只能得90分，一組執行超時)
import java.util.Arrays;
import java.util.Scanner;
public class 合併石子 {
public static void mergeStone(int[][] dp,int[] sum) {
int j=0,temp=0;
for (int i = 0; i < dp.length; i ) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
dp[i][i]=0;
}
for (int len = 2; len <= dp.length; len ) { //劃分的石子堆數
for (int i = 0; i < dp.length-len 1; i ) {
j=i len-1;
for (int k = i; k < j; k ) {
temp=dp[i][k] dp[k 1][j] sum[j]-(i==0?0:sum[i-1]);
dp[i][j]=Math.min(dp[i][j], temp);
//System.out.println(i “,” j ” : ” dp[i][j]);
}
}
}
}
public static void main(String[] args) {
Scanner scam=new Scanner(System.in);
int n=scam.nextInt();
int[] sum=new int[n];
int[][] dp=new int[n][n];
for (int i = 0; i < sum.length; i ) {
if(i==0)
sum[i]=scam.nextInt();
else
sum[i]=sum[i-1] scam.nextInt();
}
mergeStone(dp,sum);
System.out.println(dp[0][n-1]);
}
}
————————————————————————