把四堆石子合成一堆

四堆石子 [4, 1, 2, 3]，每次只能合并相邻两堆，代价是这两堆之和。求把它们合成一堆的最小总代价。运行下面这段程序：

def merge_cost(a):
    n = len(a)
    INF = 10 ** 9
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] + a[i]
    dp = [[0] * n for _ in range(n)]
    for L in range(2, n + 1):
        for i in range(n - L + 1):
            j = i + L - 1
            dp[i][j] = INF
            for k in range(i, j):
                t = dp[i][k] + dp[k + 1][j] + pre[j + 1] - pre[i]
                if t < dp[i][j]:
                    dp[i][j] = t
    return dp[0][n - 1]

print(merge_cost([4, 1, 2, 3]))