1. 问题分析

本题是一道区间dp类的模板题；
区间dp的特点是将一个区间表示成一个状态，计算时会按照按照区间长度进行枚举；

1.1 状态表示

集合(i, j): 将从第i堆石子到第j堆石子合并成一堆石子的所有方法所产生的代价；
状态f(i, j): 将从第i堆石子到第j堆石子合并成一堆石子的所有方法所产生的代价中的最小的一个；

1.2 状态计算

合并[i, j]的最小代价 = 枚举从区间[i, j]中不同位置做最后一次合并时所产生的代价，找到其中最小的一个。最后一次合并是指从两堆合并成一堆的过程；
注意计算是按照区间的长度从小到达枚举；

2. 代码实现

# 石子的堆数
N = int(input())

# 每堆石子的个数
nums = list(map(int, input().split()))

# 计算前缀和，注意前缀和索引从1开始，但数组索引还是从0开始
s = [0] * (N + 1)
for i in range(1, N + 1):
    s[i] = s[i - 1] + nums[i - 1]    

# 初始化dp数组
# dp[i][i]，只有一堆，合并代价就是0
dp = [[0] * (N + 1) for _ in range(N + 1)]


# 迭代计算
# length=1，一堆石子的合并代价就是0，前面初始化已经做好了
# 按照长度来遍历，这也是区间dp的特点
for length in range(2, N+1):

    l = 1
    while (l + length - 1 <= N):  # (l + length -1)表示的是长度为length时右边界的索引
        r = l + length - 1
        dp[l][r] = float("inf")
        for k in range(l, r):  # 将length内的石子从k, k+1中间进行合并; k+1的最大值正好是r，不会越界
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + s[r] - s[l - 1])
        l += 1

print(dp[1][N])