Dynamic programming [III] (interval DP) stone merging

Stone merging

link ：282. Stone merging - AcWing Question bank

Topic ：

Ideas ：

Code ：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=310;

int n,a[N],sum[N],f[N][N];

int main()

{

    cin>>n;

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



    // Prefix sum method 

    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];

    // Calculation [l,r] Prefix and formula for ：sum[r]-sum[l-1]

    // The interval length traverses from small to large 

    for(int len=2;len<=n;len++)// The length is 1 The time is not to merge , From 2 Start the cycle 

    {

        for(int i=1;i+len-1<=n;i++)

        {

            int l=i,r=i+len-1;

            f[l][r]=1e8;// The minimum value is required here , So the initial value is assigned a larger number 

            for(int s=l;s<r;s++)// That is, the state transition in the train of thought can be increased from the left to r-1

                f[l][r]=min(f[l][r],f[l][s]+f[s+1][r]+sum[r]-sum[l-1]);

        }

    }

    cout<<f[1][n]<<endl;

    return 0;

}