不知不觉已经第六周了，感觉什么都没学到似的，老师讲的东西有的我现在还没消化，以至于我感觉已经跟不上老师的进度，这其实很悲哀，对于DP的有些东西我还是理解不了，为什么这个状态转移方程可以这样写？为什么可以这样找状态？为什么这个问题我没想到这样做？为什么这个细节我没想到？为什么我这样愚笨？   我尽力的使自己明白为什么。

背包问题老师也讲的差不多了，有时间补补关于背包的总结，今天来点新内容，关于区间dp。先写点，渐渐补充吧。

动态规划之区间DP专题

 

什么是区间DP

所谓区间dp,就是在一个区间上进行的dp， 一般通过将大区间分割成小区间进行dp。 
区间型动态规划，又称为合并类动态规划，是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的区间中哪些元素合并而来有很大的关系。

 

区间动归状态转移方程及一般动规过程：

for k:=1 to n-1 do    //区间长度
  for i:=1 to n-k do     //区间起点
    for j:=i to i+k-1 do     //区间中任意点
      dp[i,i+k]:=max{dp[i,j] + dp[j+1,i+k] + a[i,j] + a[j+1,i+k]};

！

1. 状态转移方程字面意义：寻找区间dp[i,i+k]的一种合并方式dp[i,j] + dp[j+1,i+k]，使得其值最大或最小。
2. 区间长度k必须要放到第一层循环，来保证方程中状态dp[i,j]、dp[j+1,i+k]值在dp[i,i+k]之前就已计算出来。
3. 其中a[i,j]+a[j+1,i+k]可以不要，也可以灵活多变，指的是合并区间时产生的附加值。

区间dp伪代码：

//mst(dp,0) 初始化DP数组

for(int i=1;i<=n;i++)

{

    dp[i][i]=初始值

}

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]);

    }

}