区间dp

• 什么是区间dp？

​ 区间dp就是在***区间上进行[动态规划]***，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法

• 核心思路

  那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可

  1.可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），

  2.内层枚举该长度下可以的起点。

  3.然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解

  4.写出特定的状态转移方程(重点)

  板子

  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.区间包含的单调性：如果对于i≤i’<j≤j’，有 cost(i’,j)≤cost(i,j’)，那么说明 cost 具有区间包含的单调性。（可以形象理解为如果小区间包含于大区间中，那么小区间的cost值不超过大区间的cost值 ），证明可通过题目定义的cost(i,j)的含义进行论证

    2、四边形不等式：如果对于i≤i’<j≤j’，有 cost(i,j)+cost(i’,j’)≤cost(i’,j)+cost(i,j’)，我们称函数 cost 满足四边 形不等式。（可以形象理解为两个交错区间的cost的和不超过小区间与大区间的cost的和——(交叉小于包含)）

  • 两个定理：
    1、如果上述的cost 函数同时满足区间包含单调性和四边形不等式性质，那么函数 dp也满足四边形不等式性质 我们再定义s(i,j)表示dp(i,j) 取得最优值时对应的下标k（即 i≤k≤j 时，k 处的 dp 值最最优，则 s(i,j)=k）。此时有如下定理:
    2、假如 dp(i,j) 满足四边形不等式，那么 s(i,j)(自变量为i、j两个变量) 单调，即s(i,j)≤s(i,j+1)≤s(i+1,j+1)

  即原来的状态转移方程可以改写为下式：
  dp(i,j)=min{dp(i,k-1),dp(k,j)}+cost(i,j)(s(i,j-1)≤k≤s(i+1,j))

  for(int len=2;len<=n;len++) {	//枚举长度
     		for(int i=1;i<=n-len+1;i++) {
     			int j=i+len-1;	//根据起点推终点
     			dp[i][j]=Integer.MAX_VALUE;	//初始化值
     			for(int k=s[i][j-1];k<=s[i+1][j];k++) {	//通过平行四边形优化，缩小枚举范围
     				if(dp[i][k]+dp[k+1][j]+cost[j]-cost[i-1]<dp[i][j]) {	//换成if语句，可以减少不必要的循环赋值
     					dp[i][j]=dp[i][k]+dp[k+1][j]+cost[j]-cost[i-1];
     					s[i][j]=k;	//记录最优分割点
     				}
     			}
     			
     		}
     	}