[数据结构与算法]石子合并-区间dp

题目描述

有 n 堆石子排成一排，每堆石子有一定的数量。现在我们要将 n 堆石子并成为一堆，每次只能合并相邻的两堆石子，合并的花费为这两堆石子的总数。经过 n?1 次合并后会成为一堆，求总的最小花费。

输入描述

第一行输入一个 n ,代表石子的数量。

第二行输入 n 个整数a1?,a2?,a3?...an? ，ai? 代表第 i 堆石子的数量 。

1<=n<=1000,1<=ai<=10^5

输入输出样例

示例 1

输入

4
4 5 9 4

输出

44

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

思路

状态定义：定义dp[i][j]为合并区间第i堆到第j堆的最小花费

状态转移：我们采用自顶而下的思想。计算大区间[i,j]的最小值时，合并他的两个子区间[i.k]和[k+1,j]即可，对所有可能的合并（i ≤ k < j，即 k 在 i 、j 之间滑动），返回那个最优的合并。

先初始化dp[i][i]=0,即单个石堆合并无花费，再从区间长度=2开始合并，从小区间合并到大区间，每次增加区间长度。区间为i的状态可以由区间为i-1的状态推导而来。我们得到状态转移方程

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum1[j+1]-sum1[i])

在本体中采用前缀和的方式计算i到j的总的石子数。sum1[j+1]-sum1[i]就是合并当前区间的花费。最终，我们打印输出dp[0,n-1]，这就是从第一堆到第n堆的最小花费。

代码

n=int(input())
s=list(input().split())
sum1=[0]*(n+1) #前缀和
for i in range(n):
    sum1[i+1]=sum1[i]+int(s[i])

dp=[[float('inf')]*n for _ in range(n)]
for i in range(n):
    dp[i][i]=0

for l in range(2,n+1):
    for i in range(n):
        j=i+l-1
        if j >= n: break
        for k in range(i,j):
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum1[j+1]-sum1[i])

print(dp[0][n-1])