递推

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[105];
int sum[105];     // sum[i]: a[1]~a[i] 之和
int dp[105][105]; // dp[i][j] 表示 a[i]~a[j] 合并成一堆的最小消耗
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // sum
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + a[i];
    // dp
    memset(dp, 0x3f, sizeof(dp));
    for (int len = 1; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;
            // 计算dp[l][r]
            if (len == 1)
            {
                dp[l][r] = 0;
                continue;
            }
            for (int k = l; k < r; k++) // 讨论区间划分点
            {
                // 当前的方案：
                // 先把 a[l]~a[k] 合并成一堆 : 最少消耗 dp[l][k]
                // 再把 a[k+1]~a[r] 合并成一堆 : 最少消耗 dp[k+1][r]
                // 最后把这两堆合并在一起
                dp[l][r] = min(dp[l][r],
                               dp[l][k] + dp[k + 1][r] + (sum[r] - sum[l - 1]));
            }
        }
    cout << dp[1][n] << "\n";
    return 0;
}

记忆化搜索

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[105];
int sum[105];     // sum[i]: a[1]~a[i] 之和
int dp[105][105]; // dp[i][j] 表示 a[i]~a[j] 合并成一堆的最小消耗
// 返回 a[i]~a[j] 合并成一堆的最小消耗
int dfs(int l, int r)
{
    if (dp[l][r] != -1)
        return dp[l][r];
    if (l == r)
        return dp[l][r] = 0;
    dp[l][r] = 0x3f3f3f3f3f3f3f3fLL;
    for (int k = l; k <= r - 1; k++) // 分界点
        dp[l][r] = min(dp[l][r],
                       dfs(l, k) + dfs(k + 1, r) + sum[r] - sum[l - 1]);
    return dp[l][r];
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // sum
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + a[i];
    // dp
    memset(dp, -1, sizeof(dp));
    cout << dfs(1, n) << "\n";
    return 0;
}