区间dp

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

区间dp

概述

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

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

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

技巧与考法

破环为链

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

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

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

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

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

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

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

  • dp转移的时候枚举左右端点的时候二者的范围都是[1,2n][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][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很简单,甚至我们感受不到它的存在,但是当问题复杂的时候,从图的角度去思考和实现可能会更有利于解决问题,比如显式地维护状态之间的关系,用图存起来合法的转移,在枚举转移时只需要枚举合法的转移即可。而记忆化的话,自带寻找其拓扑序中的前序的性质。

石子合并类