博客

各类dp的总结+例题

  • Post author:
  • Post category:其他




前言

这是一篇自己对各类动态规划和动态规划技巧的总结，未完待续，后续会一边刷题一边添加内容



关于填表法和刷表法

在我们做的题中，一般填表法用得较多，但两者各有好处

一般来说动态规划中，状态的转移可以理解成图论中的一条有向边(



u

→

v

u \rightarrow v






u




→








v





)，我们以

u

作为已求出来的状态，

v

为需要求的状态，那么填表法便是将目光放在

v

上，去寻找已知的

u

来更新；而刷表法则是将目光放在

u

上，利用已知的

u

来去更新可抵达的 状态

v

具体来说填表法会写成这样 ：

dp[i] = dp[i - j] + w

而刷表法会写成这样：

dp[i + j] = dp[i] + w

填表法的

好处

不多说，毕竟平时用得最多的便是填表法

而刷表法的

好处

便是：一般对于一道题中，若是在求本状态时，寻找需要利用到的状态比较困难时，则可以考虑用刷表法



关于空间优化

动态规划中，真要考起动态规划来，感觉很少卡空间，但还是说说吧

一般我碰见比较常见的空间优化的方式有两种：

一种是状态转移时，

本状态的维度只用到了上一个状态的维度

，即

dp[i][x] = dp[i - 1][y]

这种形式，这样的优化方式有很多，例如开数组时将那一维开成2的大小，又例如直接把那一维删了

另一种

是多维度状态数组超内存

的情况，一般来说这种的特点是，有一维可以利用其它几维间接推出来，固优化方式是直接将那一维删了，然后转移时，那一维的信息直接利用其它维信息推出来。例题

[NOIP2010]乌龟棋

: 本题不能直接开5维度的空间



关于状态转移——tmp数组

为什么要总结这个？个人感觉这个真的很重要，在树形背包的应用上有

奇效

tmp数组只是我自己的叫法，具体怎么用得慢慢解释

对于上述所说的 “本状态的维度只用到了上一个状态的维度” 的空间优化，有人是这么处理的 

int dp[2][N]; //  声明
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        dp[i & 1][j] = max(dp[i & 1][j], dp[!(i & 1)][j - x] + y);
    }
}

但如果使用tmp数组则可以这样，有两种方式 

int dp[N], tmp[N]; // 声明
/* 方式一 */
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) tmp[j] = dp[j]; // 先复制，记录没转移前的状态
    for (int j = 1; j <= m; ++j) {
        dp[j] = max(dp[j], tmp[j - x] + y); // 在转移
    }
}
/* 方式二 */
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) tmp[j] = -inf; // 先初始化
    for (int j = 1; j <= m; ++j) {
        tmp[j] = max(tmp[j], dp[j - x] + y); // 再转移
    }
    for (int j = 1; j <= m; ++j) dp[j] = tmp[j]; // 最后复制回dp数组里面
}

使用tmp数组的好处是思路清晰，处理简单

注意，方式一和方式二各有好处，不同题目的初始条件不同两者的效果可能会不同



关于更新状态

寻常来说我们更新状态直接利用递推便可

但有些题目最终利用到的状态并没有多少，但直接递推又不好找转移的状态，并且直接递推复杂度可能顶不住

固一般来说这样的状态转移可以考虑记忆化搜索，类似剪枝一般在寻找状态时只搜索自己需要用到的状态，同时，有时状态可能是无限的，也可能超出了数组的下标承受范围，则可以考虑使用map存储状态



关于时间复杂度

一般来说，我们dp的时间复杂度可以从空间大小来推测，因为一般我们的状态若是几乎都要遍历一遍的话，其复杂度的下限便是其空间的大小



关于寻找具体方案

对于这种题目，求最后的答案时可以像寻常般进行dp，而反过头来求出答案来源的具体方案我一般是dfs往回找，时间负责度也不高

对于求解对字典序有要求的具体方案，我会反过来dp，然后正过来dfs找具体方案

当然，也看过别的求解具体方案的方式：多开一个数组记录转移的路线，然后像是遍历图一样找路线



线性dp



线性dp——背包

对于背包真的不想多说了，刷多了自然有就感觉了，我的《背包问题》这篇博客我也总结得不少了



例题


其他线性dp

线性dp是最基础的dp，其他dp可以说是他的延伸，线性dp难起来一般的难点是转移上

线性dp考点有很多，包括空间优化，状态转移和定义，寻找具体方案等

多刷题才是王道



例题



区间dp

一种具有区间性质的dp，一般来说转移都是从小区间转移到大区间，固一般是先枚举小区间再枚举大区间的即

dp[l][r] <- dp[l + 1][r - 1]

有两种遍历方式可以做到 

//1 比较常见的
for (int len = 1; len <= n; ++len) {
    for (int l = 1, r = l + len - 1; r <= n; ++l, ++r) {
        // 转移
    }
}
//2 可以反向l只会找l+1转移，r只会找r-1转移，固可以l逆着遍历，r顺着遍历
for (int l = n; l >= 1; --l) {
    for (int r = l; r <= n; ++r) {
        // 转移
    }
}

两种效果差不多

对于环形的区间dp，一般的处理方式是拆环成链，开两倍的空间



例题



树上dp

个人感觉，树上dp和树上背包是不一样的，固分开来写

树形dp简单的来说就是在树上进行dp

但有些模型个人觉得还是必须要去了解的

例如

  • 树上独立集
  • 树的最小支配集
  • 树的最小点覆盖
  • 树的直径
  • 树的重心

    • 性质如下
    • 一棵树最少有一个重心，最多有两个重心，若有两个重心，则他们相邻（即连有直接边）
    • 树上所有点到某个点的距离和里，到重心的距离和最小；若有两个重心，则其距离和相同
    • 若以重心为根，则所有子树的大小都不超过整棵树的一半
    • 在一棵树上添加或删除一个叶子节点，其重心最多平移一条边的距离
    • 两棵树通过连一条边组合成新树，则新树重心在原来两棵树的重心的连线上
  • 树的中心
  • ……

当然还有比较常见的便是换根dp和基环树dp

对于换根dp，换根时个人觉得还是多开一个数组进行记录需要的答案比较好。一般来说思考换根的公式是画图和进行未换根前的公式转换



例题



树形背包

树形背包，顾名思义是在树上的或者说是有依赖的背包问题

对于思考方式可以看看之前写的《树形背包思考方式》

一般困难点便是转移的思考、如何定义状态、边和点权哪个是物品重量等

当然还有一个进阶考法是利用

虚树

进行优化



例题



状压dp

状态压缩一般指的是利用二进制进行状态的压缩，很少出现三进制这些

当然状态压缩dp常见的考点便是哈密顿通路的模型

注意一个二进制状态寻找子集的搜索方法，其复杂度是O(



3

n

3^n







3










n












)的 

for (int s1 = s; s1; s1 = (s1 - 1) & s) {
    int s2 = s ^ s1;
    // s1 与 s2 互为 s 的补集
}


例题



数位dp

说起数位dp，求解的过程更像是在树上计数一样

值得注意的是：记忆化递归求解简单易懂，而且几乎不会卡递归的方式

给出递归时的一个套路代码（很多地方更多的是希望根据题意来）

有时候有些数位dp可能对前导0或者前面填的数对后面有影响，则可以在dfs中传参传多几个标志，然后在更新res（12行）时特判就好了

当然，个人感觉核心代码就是11~13行内部的转移方式，一般来说，写题的时候有点纠结状态怎么定义时，会先写这部分 

int num[100], dp[100];

int dfs(int indx, int limit, /*参数根据题意来添加*/) {
    if (indx == 0) {
        return 1;// 根据题意来返回
    }
	int &ref = dp[indx];
    if (!limit && ref != -1) return ref;
    int res = 0;
    int up = (limit ? num[indx] : 9);
    for (int i = 0; i <= up; ++i) {
        // 更新res
		dfs(indx - 1, limit && i == up);
    }
    if (!limit) ref = res;
    return res;
}

int solve(int x) {
    if (!x) return 1; // 根据题意来决定返回值
    int len = 0;
    while (x) {
        num[++len] = x % 10;
        x /= 10;
    }
    return dfs(len, 1);
}
int main() {
    memset(dp, - 1, sizeof dp); // 根据题意决定初始化的时机和大小
    // 此行省略读入
    cout << solve(r) - solve(l - 1) endl;
}


例题

~持续更新中……


版权声明：本文为hao_6_6原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。