区间dp : 循环求值之前要保证需要用到的dp值已知，故按区间长度从小到大循环

状态表示： dp[i][j] 将第i堆到第j堆的石子合并的最小代价

状态转移： 按最后一步合并的位置([l, k] [k + 1, r])划分

#include <iostream>
using namespace std;

const int NN = 310;
int N, dp[NN][NN];   // 坑点：求最小值，所以不能默认初始化为0
int a[NN];  

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 i = 1, j; (j = i + len - 1) <= N; i ++){  //  区间起点:i  终点:j
            dp[i][j] = 0x3f3f3f3f;  // 所有长度大于1的区间都初始化为正无穷
            for (int k = i; k <= j - 1; k ++){ // 区间分割 [i, k] [k + 1, j]
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + a[j] - a[i - 1]);
            }
        }
    }
    cout << dp[1][N];

    return 0;
}