上期，我们讲解了树形DP，通过搜索和DP相结合来解决问题。现在，我们将要摆脱搜索的束缚，真正探索动态规划的世界。
今天，我来向大家讲解一下区间动规的问题模型和解决方法。
首先，顾名思义，区间动规所要解决的问题是在一个序列上的，每一个区间都是一个子问题，这些子问题最后一同构成最终的问题。
按照套路，我们应该先解决子问题，再解决父问题。那显然应该按区间的大小从小到大进行处理。显然，只有一个元素的时候，应该是很容易得到答案的。
接下来，我通过几道例题加深大家对区间动规的理解（例题来源洛谷，侵删）。
洛谷P1880
这道题是区间动规的经典题目。
阅读题目，我们发现所有石子排成一列（问题在一个序列上），每次合并两对石子（区间子问题），所以显然是一个区间动规的问题。
那么怎么解决呢？
如果一段区间要合并，那么肯定是先将这段区间的两个子区间合并成两堆，再将这两堆合并。一个问题是不是就转换成两个子问题了呢？
我们可以定义f[i][j]表示把第i个石子到第j个石子合并成一堆可以得到的最大价值，转移方程很容易能得到：
最小值同理，自己试一试吧。
洛谷P3205
这是一道很有意思的题目【笑】。
这道题有两个序列，分别是初始序列和最终序列，那么我们要拿哪一个来DP呢？
考虑初始序列，这题需要我们统计初始序列的方案树，那么初始序列子区间的状态不能用两个端点来表示，还需要其他的数据还记录子区间。如果状态太多，显然时间上是不可接受的，所以用初始序列来DP行不通。
如果用最终序列来DP可行吗？
我们发现最终序列是一个固定，而且根据题意，队形的排出是从一个元素逐渐拓展成最终序列的过程。我们通过两个端点和当前序列最后进入的人排在最左边还是最右边，就能表示出一个区间的信息（因为区间内部，除了端点，其他数据都没用）。所以用最终序列来DP是可行的。
我们定义f[i][j][0/1]表示i到j这个区间最后进入的人在最左边（最右边）的方案数，转移方程很容易得到：
总结，区间DP的关键点在于找到用于DP的区间。这个区间应该要容易表示，否则时间复杂度会过高。
【信息学竞赛从入门到巅峰】，一个专注于分享OI/ACM常用算法及知识的公众号。
