补一下昨天（前天）的博客：区间dp
众所周知，dp有三个特征（条件）：1、重叠子问题；2、最优子结构；3、无后效性（这里不一一解释了）
dp的三个要素：
1、状态（一般状态、目标状态）
2、阶段划分
3、决策（状态转移）
现在我们将这些规则转移到区间dp里来：
区间dp：求区间内的最优解——小阶段dp->大阶段dp
阶段划分：区间长度
状态表示：枚举起点（不同起点、不同状态）
决策实现：枚举分割点
主要step：：
1、切割||合并区间
大区间无脑切割成两个子区间，分贝计算两个子区间的最优值，在通过两个子区间的最优值计算出大区间的最优值；
2、last原则
永远不要考虑第一步会怎么做，而是去向最后一步要干什么，然后枚举最后一步所有情况，并缩小区间
3、创建辅助维
当二维空间已经无法进行状态转移或表示状态时，可尝试增加维度
模版：
迭代模版
for(int len=2;len<=n;len++)
{//len表示区间长度
for(int i=1;i<=n;i++)
{
int j=i+len-1;//i为起点,j为终点
if(j>n)
break;
for(int k=1;k<j;k++)//枚举分割点，实现状态转移
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);//w数组代表区间和
}
}记忆化dfs模版
int mindfs(int l,int r)
{
if(dp[l][r]!=inf)
return dp[l][r];//若已搜索过则返回这个值
if(l==r)
return dp[l][r]=0;//若l==r，则无需合并，返回
for(int i=l;i<r;i++)//枚举所有可行的区间分割方案
dp[l][r]=min(dp[l][r],mindfs(l,i)+mindfs(i+1,r)+w[l][r]);//w为区间和
return dp[l][r];
}P1775 石子合并（弱化版）
一道简简单单的模版题
不过一开始要注意dp[i][i]要赋值0！！因为第i堆和第i堆合并需要的确只有0花费
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int N=1e3+5;
int n;
int m[N];
int dp[N][N];
int w[N];
int main()
{
cin>>n;
memset(dp,inf,sizeof(dp));
for(int i=1;i<=n;i++)
{
cin>>m[i];
dp[i][i]=0;
}
for(int i=1;i<=n;i++)
w[i]=w[i-1]+m[i];
for(int l=2;l<=n;l++)
for(int i=1;i<=n;i++)
{
int j=i+l-1;
if(j>n)
break;
for(int k=i;k<j;k++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[j]-w[i-1]);
}
cout<<dp[1][n]<<endl;
return 0;
}身体不适，未完待续。。。
