区间DP

区间DP主要是把一个大区间拆分成几个小区间，先求小区间的最优值，然后合并起来求大区间的最优值。
一般区间DP实现代码：

memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++） //区间长度为1的初始化
    dp[i][i] = 0;
for (int len = 2; len <= n; len++) //枚举区间长度，当i=1;len=2;j=len;时区间长度为1，在下面的循环中长度不变。然后下面循环结束后len++区间长度变大。
{
    for (int i = 1, j = len; j <= n; i++, j++) //区间[i,j]
    {
        //DP方程实现
    }
}

当然在给定区间查找时有时候要用到中间变量k:
例：
石子合并一条直线上有N堆石子，现在要将所有石子合并成一堆，每次只能合并相邻的两堆，合并花费为新合成的一堆石子的数量，求最小的花费。
1堆，花费为0
2堆，花费为sum[2]
3堆，花费为min(a[1] + a[2], a[2] + a[3]) + sum[3]
如果我们有n堆，合并的最后一次操作一定是从两堆合并成一堆.

规定dp[i][j]为合并第i堆到第j堆的最小花费
DP方程为：
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);(i <= k < j)

另外关于区间DP有的时候不能用正向思路解题，可以将思路逆向得到区间DP问题：
例：
题意：给你若干张卡片，第i张卡片的分值为Score[ i ] ( 1 <= i <= N )。现在游戏如下，给定N张卡片，除了第一张和最后一张卡片不可取之外，你可任取一张，得到分值Score[ i – 1] * Score[ i ] * Score[ i + 1 ]，然后就把这张卡片去掉。题目要求最后计算最小的总得分。
分析：把这道题倒过来看，每次向这个数列里面添加数的话，就会拿到这样的模型：首先向两个数a，c中间加上一个数b，然后剩下的数字只能加到a，b中间或者b，c中间，这样，就得到了一个动态规划的策略，转移方程为：dp[a][c] = dp[a][b] + dp[b][c] + s[a]*a[b]*s[c],如果在a和c中间遍历b，就可以得到dp[a][c]的值。

“无穷大”值的设置：

可以把INF设为0x7fffffff，这是32-bit int的最大值。
但是如此设置便有一个缺陷，当两个无穷大相加时，会出现溢出情况，导致结果变成很小很小的负值。因此这种设置可以用来比较，但并不适合拿去运算。
因此我们可以使用：0x3f3f3f3f。
0x3f3f3f3f的十进制是1061109567，是109级别的（和0x7fffffff一个数量级），而一般场合下的数据都是小于109的，所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。 （例：0x3f3f3f3f+0x3f3f3f3f=2122219134）
如果我们想要将某个数组清零，我们通常会使用memset(a,0,sizeof(a))，方便又高效，但是当我们想将某个数组全部赋值为无穷大时，就不能使用memset函数而得自己写循环了，因为memset是按字节操作的，它能够对数组清零是因为0的每个字节都是0（一般我们只有赋值为-1和0的时候才使用它）。但是现在好了，如果我们将无穷大设为0x3f3f3f3f，0x3f3f3f3f的每个字节都是0x3f。所以要把一段内存全部置为无穷大，我们只需要memset(a,0x3f,sizeof(a))。
类似地，将数组清为最小值时，可以使用：
memset(a,0x8f,sizeof(a));