区间dp，顾名思义就是在一段区间上进行动态规划。对于每段区间，他们的最优值都是由几段更小区间的最优值得到，是分治思想的一种应用，将一个区间问题不断划分为更小的区间直至一个元素组成的区间，枚举他们的组合 ，求合并后的最优值。
for(int i=1;i<=n;i++) dp[i][i]=初始值 //或memset(dp,0,sizeof(dp)) 初始化DP数组 for(int len=2;len<=n;len++) //区间长度 for(int i=1;i<=n;i++) //枚举起点 { int j=i+len-1; //区间终点 if(j>n) break; //防止越界 for(int k=i;k<j;k++) //枚举分割点，构造状态转移方程 { dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]); } }
模板题：poj2955 https://www.cnblogs.com/-citywall123/p/10896480.html
原文：https://www.cnblogs.com/-citywall123/p/10896457.html