試題 算法提高 合并石子（動(dòng)態(tài)規(guī)劃）
時(shí)間限制：2.0s 內(nèi)存限制：256.0MB
問題描述
在一條直線上有n堆石子，每堆有一定的數(shù)量，每次可以將兩堆相鄰的石子合并，合并后放在兩堆的中間位置，合并的費(fèi)用為兩堆石子的總數(shù)。求把所有石子合并成一堆的最小花費(fèi)浩嫌。
輸入格式
輸入第一行包含一個(gè)整數(shù)n檐迟，表示石子的堆數(shù)。
接下來一行码耐，包含n個(gè)整數(shù)追迟，按順序給出每堆石子的大小 。
輸出格式
輸出一個(gè)整數(shù)骚腥，表示合并的最小花費(fèi)敦间。
樣例輸入
5
1 2 3 4 5
樣例輸出
33
數(shù)據(jù)規(guī)模和約定
1<=n<=1000, 每堆石子至少1顆，最多10000顆束铭。
思路：
題目意思就是在n堆石子中不斷的合并相鄰的石頭直到合并成1堆廓块，然后叫我們算出最小花費(fèi)。題目的花費(fèi)情況是合并的費(fèi)用為兩堆石子的總數(shù)契沫，意思就是當(dāng)我們合并1和2 那么花費(fèi)就是3 合并的3和之前的3合并花費(fèi)總和就是3+3+3=9還要加之前的花費(fèi)带猴。
那我們可以分解此題，假設(shè)我們有1個(gè)石頭那花費(fèi)是0懈万，2個(gè)石頭那么就是他們的總和拴清，3個(gè)石頭那我們?cè)趺磩澐帜兀覀兛梢园阉纸獬鰜? ：
第一種
我們可以將前面（第1堆和第2堆合并的花費(fèi)值+第3堆花費(fèi)值）+他們3個(gè)石頭的數(shù)量=總花費(fèi)值 （因?yàn)榛ㄙM(fèi)值并沒有把本身的石頭值加到花費(fèi)里面会通。）
第二種
（第2堆和第3堆合并的花費(fèi)值+第1堆花費(fèi)值）+他們3個(gè)石頭的數(shù)量=總花費(fèi)值 依次類推.....
那我們從上面可以知道可以用動(dòng)態(tài)規(guī)劃的方式完成口予。
我們可以先把第1堆到n的每個(gè)區(qū)域儲(chǔ)存起來我存儲(chǔ)到了ad列表中。我們?cè)诮⒁粋€(gè)dp[j][j1]表示j-j1之間的最小花費(fèi)渴语。
我們建立2層for循環(huán)第一層表示長(zhǎng)度 第二層表示當(dāng)前開頭的堆 那 堆尾=開頭+長(zhǎng)度
從上述可知我們需要把這n堆石子的可能性列出來。那我們就建立一個(gè)for 從j-j1 因?yàn)槲覀儽闅v的是當(dāng)前的n堆的可能性昆咽，那么dp[j][k] 表示的是前面j-k的堆 后面那么就表示 dp[k+1][j1], 這就是我們合并所花費(fèi)的值驾凶。并沒有把本身的石頭值加到花費(fèi)里面。所以還要加ad[j1]-ad[j-1].
那么我們的轉(zhuǎn)移方程就是：dp[j][k]+dp[k+1][j1]+ad[j1]-ad[j-1]
然后在和本身的數(shù)比較最小值：
min(dp[j][j1],dp[j][k]+dp[k+1][j1]+ad[j1]-ad[j-1]) 注意我是從1開始的掷酗。
程序：
n=int(input())
a=list(map(int,input().split()))
dp=[[999999999999 for i1 in range(n+5)] for i in range(n+5)] #dp初始化
ad=[ 0 for i in range(1005)]
for i in range(1,n+1):
ad[i]=ad[i-1]+a[i-1] #把第0堆到i的每個(gè)區(qū)域儲(chǔ)存起來
dp[i][i]=0 #1堆最小花費(fèi)為0
for i in range(1,n+1): #表示j+i之間的堆 可以說是當(dāng)前的長(zhǎng)度调违。
for j in range(1,n-i+1): #當(dāng)前開頭堆
j1=i+j #結(jié)尾堆
for k in range(j,j1+1): #把這n堆石子的可能性列出來
dp[j][j1]=min(dp[j][j1],dp[j][k]+dp[k+1][j1]+ad[j1]-ad[j-1])
print(dp[1][n])
禁止轉(zhuǎn)載。僅用于自己學(xué)習(xí)泻轰。對(duì)程序錯(cuò)誤不負(fù)責(zé)技肩。
