一：原理

具有明显的阶段性（相邻的合并），所以只能区间dp，不能贪心
核心就是相邻的堆合并，无论是一个什么范围一定是最后两个区间合并，利用这个原理，去找状态转移方程。

二：代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;
int f[N][N], a[N]; 
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    for (int len = 2; len <= n; len++) // 精髓之处***，因为先按照长度从小到大的处理
        for (int l = 1; l + len - 1 <= n; l++)
        {
             r = l + len - 1; // 按照长度遍历构造区间
            f[l][r] = 0x3f3f3f3f; // bug解释的很清楚
            for (int k = l; k < r; k++)
            {
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + a[r] - a[l - 1]);
            }
        }
    cout << f[1][n] << endl;
    return 0;
}

三：bug

• 区间合并的边界问题，本来想memset，直接全部初始化，但是实际执行的时候，必须f[i][i] = 0， 否则下面

f[k + 1][r]这里两个堆的时候就是f[r][r]，初始化时最大值，这样就没有结果了，所以必须f[i][i] = 0；

• 逻辑上上面的写法的话更简洁明了一些，我本来就是利用第三层循环求解f[i][j]的最小值，直接初始化最大，这样就避免全局变量是0. ```cpp

  include

  include

  include

using namespace std;

const int N = 310;

int f[N][N], a[N]; int n;

int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; a[i] += a[i - 1]; } memset(f, 0x3f, sizeof f); for (int len = 2; len <= n; len++) for (int i = 1; i + len - 1 <= n; i++) { int l = i, r = l + len - 1;

        for (int k = l; k < r; k++)
        {
            f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + a[r] - a[l - 1]);
        }
    }
cout << f[1][n] << endl;
return 0;

} ```