试题 算法提高 合并石子（动态规划）

时间限制：2.0s 内存限制：256.0MB
问题描述
　　在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。
输入格式
　　输入第一行包含一个整数n，表示石子的堆数。
　　接下来一行，包含n个整数，按顺序给出每堆石子的大小 。
输出格式
　　输出一个整数，表示合并的最小花费。
样例输入
5
1 2 3 4 5
样例输出
33
数据规模和约定
　　1<=n<=1000, 每堆石子至少1颗，最多10000颗。
思路：
题目意思就是在n堆石子中不断的合并相邻的石头直到合并成1堆，然后叫我们算出最小花费。题目的花费情况是合并的费用为两堆石子的总数，意思就是当我们合并1和2 那么花费就是3 合并的3和之前的3合并花费总和就是3+3+3=9还要加之前的花费。
那我们可以分解此题，假设我们有1个石头那花费是0，2个石头那么就是他们的总和，3个石头那我们怎么划分呢，我们可以把他分解出来 ：
第一种
我们可以将前面（第1堆和第2堆合并的花费值+第3堆花费值）+他们3个石头的数量=总花费值 （因为花费值并没有把本身的石头值加到花费里面。）
第二种
（第2堆和第3堆合并的花费值+第1堆花费值）+他们3个石头的数量=总花费值 依次类推.....
那我们从上面可以知道可以用动态规划的方式完成。
我们可以先把第1堆到n的每个区域储存起来我存储到了ad列表中。我们在建立一个dp[j][j1]表示j-j1之间的最小花费。
我们建立2层for循环第一层表示长度 第二层表示当前开头的堆 那 堆尾=开头+长度
从上述可知我们需要把这n堆石子的可能性列出来。那我们就建立一个for 从j-j1 因为我们遍历的是当前的n堆的可能性，那么dp[j][k] 表示的是前面j-k的堆 后面那么就表示 dp[k+1][j1], 这就是我们合并所花费的值。并没有把本身的石头值加到花费里面。所以还要加ad[j1]-ad[j-1].
那么我们的转移方程就是：dp[j][k]+dp[k+1][j1]+ad[j1]-ad[j-1]
然后在和本身的数比较最小值：
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的每个区域储存起来
    dp[i][i]=0   #1堆最小花费为0
for i in range(1,n+1):   #表示j+i之间的堆  可以说是当前的长度。
    for j in range(1,n-i+1):  #当前开头堆
        j1=i+j  #结尾堆
        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])

禁止转载。仅用于自己学习。对程序错误不负责。