关于区间DP的一点点心得（虽然还是很菜）

关于区间DP的一点点心得

1. 区间 DP 的数组一般是二维，其状态一般表示区间 \((l,r)\)。

2. 区间 DP 在思考的时候是有一定套路的，思考时可以按照如下方式进行思考：

   1. 这段区间要维护的信息是什么（即 \(dp\) 或 \(f\) 数组内的值应该存什么）？
   2. 状态的边界如何设计（这个我认为对于所有的 DP 来说，都应当是其思考过程之一）？
   3. 这段区间如何从它的更小的区间推广过来（即如何从 \(dp(l,r)\) 或 \(f(l,r)\) 的子区间转移到本身）？
   4. 怎样合并或更新信息（即如何统计信息，是取最大值还是最小值，是应该使用加法原理合并方案数还是用乘法原理）？

   对于大部分人（尤其是我）来说，以上三点基本上是区间 DP 的全部思维难点。

   对于第一条来说，如果让我们维护最大值，我们应当怎么办，维护方案个数我们又应当怎么设计维护的信息。

   对于第二条来讲，我们应当考虑一下数组的初始值应当是什么值，边界值又应当是什么值，那些情况下就到达了边界情况等等都应当被考虑，并且编写代码的时候千万不要忘了这一步，否则很有可能会莫名其妙地 WA 掉。

   而对于第三条如何推广，是通过两个子区间推广过来（即为 \(dp(l,r)\) 是从 \(dp(l,k)\) 和 \(dp(k+1,r)\) 转移而来），还是单纯的左端点减一或右端点减一推广而来（例如题目 P3205 [HNOI2010]合唱队）。

   至于第四条，就是要考虑合并子区间信息并更新区间信息时，我们如何正确的合并（例如单纯的加减），并且如何正确的更新区间信息（例如单纯的赋值），还有就是需不需要进行分类讨论，有没有什么可能会出现的坑点之类。

3. 区间 DP 的板子：
   众所周知，DP 类题目一般是没有板子的，但是根据自己那微薄的做题量分析，发现其中还是有一定的规律的，基本形式如下：

memset(dp,状态初始值,sizeof(dp));
for(int i=1;i<=n;i++)
	dp[i][i] = 状态边界值;
for(int len = 2;len<=n;++len){
	for(int l=1;l+len-1<=n;++l){
		int r = l+len-1;
		//这里写如何从子区间当中推广出来 
	}
}
cout<<dp[1][n]<<endl;//统计答案并输出（注意，这里所写的方法不唯一，在某些情况下不适用！！） 

4. 例题：
   这里先咕咕咕，马上安排