让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，我可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的起点，自然终点也就明了了。然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。
板子：
for(int len = 1;len<=n;len++){//枚举长度 for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n int ends = j+len - 1; for(int i = j;i<ends;i++){//枚举分割点，更新小区间最优解 dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something); } } }
注意要点
1.必须先枚举区间长度l否则会炸。 2.注意枚举顺序为长度=>起始点=>中间点，起始点循环开始后马上算终止节点，边界的节点应该在枚举中间节点的循环之外进行！三.朴素区间dp（n^3/2)
51nod 1021石子合并
#include<iostream>#include<cstring>//MEMSET（）函数头文件 #include<cstdio>#include<algorithm> using namespace std;#define inf 0x3f3f3fint stone[102];int dp[102][102];int sum[102];int main(){ int n;cin>>n; memset(sum,0,sizeof(sum)); memset(dp,inf,sizeof(dp)); for(int i=1;i<=n;i++) { cin>>stone[i]; sum[i]=sum[i-1]+stone[i]; dp[i][i]=0; } for(int len=1;len<=n;len++)//枚举区间长度 for(int j=1;j+len<=n+1;j++) //枚举起点 { int ends=j+len-1; for(int i=j;i<=ends;i++)//枚举分割点 { dp[j][ends]=min(dp[j][ends],dp[j][i]+dp[i+1][ends]+sum[ends]-sum[j-1]); } } cout<<dp[1][n]<<endl; return 0;}
转载于:https://www.cnblogs.com/flyljz/p/10989026.html
