一. 题目

二. 思路

1. 搜索

2. 记忆化搜索

3. DP

三. 代码

1. 搜索

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int N=310, INF=2e9;

int n;
int s[N];//前缀和数组，快速区间求和

class Search
{
public:
    Search()
    {
        initIO();
    }

    void initIO()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
    }
    
    //合并l到r石子的最小代价
    int dfs(int l, int r)
    {
        if(l==r) return 0;//单石碓代价为0
        
        //枚举l~r石子合并，从哪个分界点去合并
        int cost=INF;
        for(int k=l;k<r;++k)//k不能等于r，否则k+1有可能>r
            cost=min(cost, dfs(l, k)+dfs(k+1, r));
            
        return cost+s[r]-s[l-1];
    }
}sh;

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>s[i];
        s[i]+=s[i-1];
    }
    cout<<sh.dfs(1, n);
}

2. 记忆化搜索

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int N=310, INF=2e9;

int n;
int s[N];//前缀和数组，快速区间求和

class Search
{
public:
    int f[N][N];//记忆化数组, 记录已经搜索过的状态
public:
    Search()
    {
        initIO();
    }

    void init()
    {
        fill(f[0], f[0]+N*N, INF);
        for(int i=1;i<=n;++i) f[i][i]=0;
    }

    void initIO()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
    }

    //合并l到r石子的最小代价
    int dfs(int l, int r)
    {//f[i][i]==0了，所以不用判断l==r时的情况
        if(f[l][r]!=INF) return f[l][r];

        //枚举l~r石子合并，从哪个分界点去合并
        for(int k=l;k<r;++k)//k不能等于r，否则k+1有可能>r
            f[l][r]=min(f[l][r], dfs(l, k)+dfs(k+1, r));
        return f[l][r]+=s[r]-s[l-1];
    }
}sh;

int main()
{
    cin>>n;
    sh.init();

    for(int i=1;i<=n;++i)
    {
        cin>>s[i];
        s[i]+=s[i-1];
    }
    cout<<sh.dfs(1, n);
}

3. DP

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int N=310, INF=2e9;

int n;
int s[N];//前缀和数组，快速区间求和

class DP
{
public:
    int f[N][N];//f[i][j]表示区间i~j石子合并的代价
public:
    DP()
    {
        initIO();
        fill(f[0], f[0]+N*N, INF);
    }

    void initIO()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
    }

    int work()
    {
        for(int len=1;len<=n;++len)//枚举区间长度，从小到大
            for(int l=1;l+len-1<=n;++l)//枚举区间起点l, 同时保证r<=n
                if(len==1) f[l][l]=0;//等同于初始化
                else
                {
                    int r=l+len-1;//算出区间右端点j
                    for(int k=l;k<r;++k)//枚举分界点k,注意k<j, 否则k+1可能>j
                        f[l][r]=min(f[l][r], f[l][k]+f[k+1][r]+s[r]-s[l-1]);

                }
        return f[1][n];
    }
}dp;

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>s[i];
        s[i]+=s[i-1];
    }
    cout<<dp.work();
}