282. Stone consolidation (interval DP)

Application interval dp To think

State means ： All merged i Pile up to the third j A collection of fruits

attribute ：min

State calculation / subset division ： Which two piles of fruits were merged last time , That is, where was the last breakpoint

• The break point is i+1        Merge [i] and [i+1,j]        dp[i][j]=dp[i][i]+dp[i+1][j]+sum[i,j]
• The break point is i+2        Merge [i,i+1] and [i+2,j]  dp[i][j]=dp[i][i+1]+dp[i+2][j]+sum[i,j]
• ...
• The break point is j-1          Merge in [i,j-1] and [j]     dp[i][j]=dp[i][j-1]+dp[j][j]+sum[i,j]

initialization ： All are infinite

The border ：dp[i][i]=0

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=305;
int a[N];
int s[N];
int dp[N][N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i],s[i]=s[i-1]+a[i];
    memset(dp,0x3f,sizeof dp);
    for(int i=1;i<=n;i++)
        dp[i][i]=0;
    for(int len=2;len<=n;len++)
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            for(int k=i;k<j;k++)
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
        }
    cout<<dp[1][n];
    return 0;
}