对三个for循环的理解
将1~n堆石子合并成一堆
//用dp[i][j]堆表示将i~j堆石子合并成一堆的最小值,在合并之前,一定是由dp[i][k],
dp[k+1][j]这两堆石子
合并过来的,我们就枚举k的每一个可能取值,取其中的最小值即可i<=k<j
因此我们先由合并2堆石子最小值—>合并3堆石子最小值—>··· ---->合并n堆石子最小值
也就是先枚举合并石子的区间长度(len),然后在去枚举每个区间的k值
合并i~j堆石子的值为ai+···+aj,用前缀和求
#include<iostream>
using namespace std;
const int N=310;
int s[N];
int dp[N][N];
int n;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=1;i<=n;++i)cin>>s[i],s[i]+=s[i-1];
for(int len =2;len<=n;++len)//枚举区间长度
for(int l=1;l+len-1<=n;++l)//枚举左端点,同时右端点不能越界
{
int r=l+len-1;
dp[l][r]=1e9;
for(int k=l;k<r;++k)//i<=k<j
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
}
cout<<dp[1][n];
return 0;
}