最优合并问题的算法源码

最优合并问题是经典的动态规划问题，在这里给出其伪代码和 Python 实现。

伪代码：

OPT[i][j] = 0
for k = i to j-1:
    temp = OPT[i][k] + OPT[k+1][j] + cost[i][k] + cost[k+1][j]
    if temp < OPT[i][j]:
        OPT[i][j] = temp

其中，`OPT[i][j]` 表示将 `i` 到 `j` 这些文件合并成一个文件所需的最小代价，`cost[i][j]` 表示将 `i` 到 `j` 这些文件合并成一个文件的代价。

Python 实现：

def optimal_merge(arr):
    n = len(arr)
    OPT = [[0] * n for i in range(n)]
    for gap in range(1, n):
        for i in range(n-gap):
            j = i + gap
            OPT[i][j] = float("inf")
            for k in range(i, j):
                temp = OPT[i][k] + OPT[k+1][j] + sum(arr[i:j+1])
                if temp < OPT[i][j]:
                    OPT[i][j] = temp
    return OPT[0][n-1]

其中，`arr` 是一个列表，表示每个文件的大小。