試題 算法提高 合并石子（動(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é)。