先枚举长度，再枚举左端点，就有了右端点，最后枚举中间线

#include <iostream>
#include <algorithm>
using namespace std;

#define N 501
#define INF 0x3f3f3f3f

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

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> s[i];

    for (int i = 1; i <= n; i++)        // 求前缀和
        s[i] += s[i - 1];

    for (int len = 2; len <= n; len++)  // 枚举区间的长度
        for (int i = 1; i + len - 1 <= n; i++) 
        {
            int l = i,r = i + len - 1;  // 左端点和右端点
            f[l][r] = INF;              // 要先初始化
            for (int k = l; k <= r; k++)
                f[l][r] = min(f[l][r] , f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }

    cout << f[1][n];                    // 完美收场
    return 0;
}

拓展: 金字塔

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;

const int N = 301,mod = 1e9;

int n;
int f[N][N];
string st;

int main()
{
    cin >> st;

    n = st.size();

    if (n % 2 == 0) puts("0");
    else
    {
        for (int len = 1; len <= n; len++)
            for (int l = 0; l + len - 1 < n; l++)
            {
                int r = l + len - 1;
                if (len == 1) f[l][r] = 1;
                else if (st[l] == st[r])
                {
                    for (int k = l; k < r; k++)
                        if (st[k] == st[r])
                            f[l][r] = (f[l][r] + (LL)f[l][k] * f[k + 1][r - 1]) % mod;
                }
            }
        cout << f[0][n - 1];
    }
    return 0;
}