282.石子合并 (区间dp)

运用区间dp的思想来思考

状态表示：所有合并第i堆到第j堆果子的集合

属性：min

状态计算/子集划分：上一次合并了哪两堆果子，即上一次的中断点是哪

中断点在i+1        合并[i]和[i+1,j]        dp[i][j]=dp[i][i]+dp[i+1][j]+sum[i,j]中断点在i+2        合并[i,i+1]和[i+2,j]  dp[i][j]=dp[i][i+1]+dp[i+2][j]+sum[i,j]...中断点在j-1         合并在[i,j-1]和[j]     dp[i][j]=dp[i][j-1]+dp[j][j]+sum[i,j]

初始化：全为无穷大

边界：dp[i][i]=0

#include 
#include 
#include 
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