Interval DP chain stone merging

Problem description

N A row of stones , The number is 1,2,…,n. Each pile of stones has a pile of weight , Now combine all the stones into one pile . The cost of merging two piles of stones into one pile is the sum of the weight of the two piles of stones , The weight of the combined pile of stones is the sum of the weight of the two piles of stones . Try to find the minimum cost of merging all the stones into one pile .

Input format

Enter a number in the first line N, Represents the number of piles of stones ; Second line input N It's an integer , respectively N The weight of the stones .

Output format

The output will N The minimum cost of merging stones into a pile

Data range

1<=N<=30

sample input

4
1 3 5 2

sample output

22

Their thinking

take N The process of merging stones into a pile , In each step, two piles of stones are combined into one pile , Reduce the number of stone piles by one ; Two piles of stones merged each time , It may be from the beginning N Made up of several piles of stones .

• remember [l,r] citing (l,l+1,l+2,…,r) Merge into a pile of stones ; Each pile of stones is obtained by merging two piles of stones , be [l,r] The stone may be made of [l,k] and [k+1,r]（l<=k<r） Two piles of stones are combined to get .
• remember f[l,r] In order to get [l,r] The smallest price paid for this pile of stones ; Ruoshi [l,r] from [l,k] and [k+1,r] Two piles are merged to get , be obtain [l,r] The price paid by this pile of stones by obtain [l,k] The price paid by this pile of stones and obtain [k+1,r] This pile of stones and take [l,k] and [k+1,r] The cost of merging two piles of stones into one , So we get the recurrence formula ：

f[l,r]=min(f[l,k]+f[k+1,r]+s[r]-s[l-1]),(l<r)
f[l,r]=0,(l == r)

among ,s[i] For the former i The prefix of the weight of the rockfill and ,(l <= k < r)

• initial value ： arbitrarily i∈[1,N],f[l][l]=0, The rest is positive infinity
• The goal is ：f[1][n]

Implementation code

#include<iostream>
#include<algorithm>

using namespace std;

const int N=310;

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

int main()
{
    
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];

    // Find the prefix and 
    for(int i=1;i<=n;i++) s[i]=s[i-1]+w[i];

    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]=1e8;// Make a difference k Under the condition of f[l][r] The minimum value of , So I don't want his initial value to be affected , So set it to positive infinity 
            for(int k=i;k<r;k++)// enumeration [l,r-1] Different intervals within the range 
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
        }
    // The output result is the interval [1,n] Value 
    cout<<f[1][n]<<endl;

    return 0;
}