伪代码描述动态规划石子合并问题

假设有 $n$ 堆石子，每堆石子的数量为 $a_1, a_2, \cdots, a_n$。现在要将这些石子合并成一堆。合并时，每次可以将相邻的两堆石子合并成一堆，合并的代价为两堆石子的数量之和。假设将 $a_i$ 和 $a_{i+1}$ 合并的代价为 $c_i$，则将所有石子合并成一堆的总代价为：

$$
C = \sum_{i=1}^{n-1} c_i
$$

现在要求出将所有石子合并成一堆的最小代价。这是一个经典的动态规划问题，可以使用以下的伪代码描述：

for i in 1 to n:
    dp[i][i] = 0
for len in 2 to n:
    for i in 1 to n - len + 1:
        j = i + len - 1
        dp[i][j] = inf
        for k in i to j - 1:
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum(a[i..j]))
print(dp[1][n])

其中，$dp[i][j]$ 表示将 $a_i$ 到 $a_j$ 合并成一堆的最小代价。初始时，$dp[i][i]=0$，因为一堆石子不需要合并。然后按照石子堆数递增的顺序，依次计算 $dp[i][j]$，最后得到 $dp[1][n]$ 即为将所有石子合并成一堆的最小代价。