石子合併 動態規劃(直線型)

石子合併 動態規劃(直線型)

問題描述
  在一條直線上有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]);
}
}

————————————————————————