记录了区间dp的常见技巧与考法

区间dp

概述

区间dp也是一类线性dp，因为状态转移的时候也是线性变化的。

区间dp以区间长度为阶段，使用能足够表示区间的坐标表示状态（最常见的是使用$(l, r)$表示一维区间，但也有的题目需要使用$(x_1, y_1, x_2, y_2)$表示二维的区间状态）。

对于区间dp中最朴素的问题（比如序列上的石子合并等）此处就不多加介绍了，下面主要讲一些区间dp中常见的技巧和考法。

技巧与考法

破环为链

这个技巧常常用来做转移时需要表示环形区间的区间dp问题。

对于环形的石子合并问题，如果想用链上的石子合并做，一种朴素的想法是枚举环的起点，然后把环看成长度为$n$的链，然后在这个链上做区间dp，这样下来时间复杂度会高达$O(n^4)$。

我们不妨考虑一下在做环上的dp的时候到底实质上算过哪些状态：除了所有的$l\leq r$的状态，还计算了所有的$l > r$的状态。而枚举环的起点再做链上的dp的方式导致很多状态实际上被重复计算了。所以，实际上我们只要在倍长的链上做dp，把这条链上面所有的状态都算出来，所计算出来的结果和朴素做法是一样的，但是复杂度却是$O(n^3)$。

使用这个技巧的时候，需要特别注意的地方是：

• 开数组的时候，所有空间按照2倍来开。

• 记得倍长链，把数组往后复制一遍。

• 初始化dp数组以及做前缀和预处理等操作的时候，都需要考虑长度为$2n$的链。

• dp转移的时候枚举左右端点的时候二者的范围都是$[1, 2n]$。

注意到这几点，那么剩下的和普通的链上做法就没什么两样了。

附上一段环形石子合并求最大与最小值的示例代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 420, INF = 0x3f3f3f3f;

ll w[N], s[N], dp_max[N][N], dp_min[N][N], n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        w[i + n] = w[i];
    }

    for (int i = 1; i <= 2 * n; i++) {
        s[i] = s[i - 1] + w[i];
    }

    memset(dp_min, 0x3f, sizeof dp_min);
    memset(dp_max, 0, sizeof dp_max);

    for (int i = 1; i <= 2 * n; i++) {
        dp_min[i][i] = 0;
    }
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l <= 2 * n; l++) {
            int r = l + len - 1;
            if (r > 2 * n) break;
            for (int k = l; k < r; k++) {
                dp_max[l][r] = max(dp_max[l][r], 
                                  dp_max[l][k] + dp_max[k + 1][r] + s[r] - s[l - 1]);
                dp_min[l][r] = min(dp_min[l][r],
                                  dp_min[l][k] + dp_min[k + 1][r] + s[r] - s[l - 1]);
            }
        }
    }
    ll ans_max = -INF, ans_min = INF;
    for (int i = 1; i <= n; i++) {
        ans_max = max(ans_max, dp_max[i][i + n - 1]);
        ans_min = min(ans_min, dp_min[i][i + n - 1]);
    }
    cout << ans_min << endl << ans_max << endl;
    return 0;
}

开/闭区间状态设计

最符合人的思考习惯的区间dp的状态设计是设dp[l][r]为$[l, r]$状态下某个决策集合的某个属性，但是也有一些问题不适合使用闭区间来表示状态，反而使用半开半闭或者全开区间更加符合人的习惯，当然，这个时候要注意几件事情：

• 初始化
• 转移方程的中间如何划分（dp[k][r]还是dp[k + 1][r]）
• 右端点到底枚举到多少
• 最后的结果到底是多少（dp[i][i + n - 1]还是dp[i][i + n]）

方案记录

类似于一般的线性dp，对于每个状态dp[l][r]，维护一个转移变量mark[l][r]，记录该状态是由哪个dp[l][k]和dp[k + 1][r]（也可能是dp[k][r]，看自己的状态定义了）转移过来的。这样对于dp[1][n]，可以找到划分点，然后递归地去划分，最终输出结果。可以看到这个过程隐含着一个树形结构，所以有时候题目会让我们按照前序（或者其他序）遍历输出最终结果。

注意对于元区间的方案的初始化。

与高精度结合

其实啥dp都可以和高精度结合，只要数够大。

一般的做法是先用int或者long long做对转移，然后写几个高精度计算和比较的函数，最后把dp数组以及计算过程逐个替换就好了。

在实现上，一个高精度数可以用一个vector<int>来表示，对高精度数的运算的实现确保能用高精乘低精就用高精乘低精，不行了再写双高精。

二维/高维区间dp

这里就是最开始提到的，需要用好几个坐标才能表示一个高维区间，比如一个矩形块。除了状态升维之外，转移的方向也变多了，可能可以横着划分转移，可以竖着划分转移。

其实高维区间是一个抽象概念，指的是单纯用一个数没法描述一个端点的所有信息的区间。涉及到高维区间的时候，可能状态转移的顺序上会笔记较难考虑。

在实现上，从元区间到更大的区间不容易确定枚举顺序时，可以考虑记忆化搜索实现dp。

在做这种记忆化搜索好实现的dp题目的时候，我总是能深深地感受到dp和图论之间的深刻联系。事实上，dp的状态 + 转移构成了一个DAG，我们平时的递推就是在这个DAG上沿着边做的。我们见过的相当一部分dp题目的DAG很简单，甚至我们感受不到它的存在，但是当问题复杂的时候，从图的角度去思考和实现可能会更有利于解决问题，比如显式地维护状态之间的关系，用图存起来合法的转移，在枚举转移时只需要枚举合法的转移即可。而记忆化的话，自带寻找其拓扑序中的前序的性质。

石子合并类