常见dp问题

dp的引入

动态规划(简称dp), 是指把一个问题分解为若干个子问题, 通过局部最优解得到全局最优的一种算法策略或者说一种思想方法. 简单来讲, 就是用一个数组表示我们要求的问题的答案, 如果知道前一个问题的答案, 就可以推出后一个问题的答案

dp有以下几个常见的概念:

1. 状态: 指当前所考虑的子问题的情况. 例如背包的已用体积, 区间的起止点, 以及用状态压缩手段压缩后的状态
2. 状态转移: 指由前一个子问题的答案推出当前问题的答案. 一般来讲会由一个表示赋值的等式给出, 称为状态转移方程
3. 无后效性: 指当前子问题的处理策略与后边问题的解答无关. 要记住我们是从子问题的答案推出新问题的答案, 与这个子问题的答案怎么来无关

dp一般有以下三个步骤:

1. 设计状态: 指设计出合适的dp数组以及规定dp数组的含义. 设计出的dp数组要能够形容各种状态并且能无后效性地在状态之间进行转移
2. 推理状态转移方程: 顾名思义, 关键在于如何从已知问题的答案推出当前问题的答案, 有的时候需要多个方程, 有的时候一个方程要包含多个子状态
3. 确定边界条件: 递推的初值或者说记忆化搜索的回溯条件, 以及各个数组的初值

基础线性dp

线性dp往往指在一个序列上进行的dp, 当然也可能有两个甚至多个序列. 一般来讲, 线性dp的三个步骤分别有以下特点:

设计状态: 至少有一维表示当前考虑的对象在数列上的位置

状态转移: 必须找到这条线上前面的位置的dp值来推出当前位置的dp值

边界条件: 第一个位置单独讨论

基础区间dp

区间dp可以视作线性dp的一个分支, 之所以把它单独列出来是因为区间dp的解法比较特殊, 同时也比较固定. 区间dp与其他线性dp不同的地方在于它的状态是以序列上的一个区间来表示的, 而且大区间的答案可以由小区间的答案得到

区间dp的基本思路:

设计状态: 至少要有 dp[l][r] 两维分别表示区间的左端点和右端点

状态转移: 一般通过枚举区间 [l,r] 之间的点 k 把 [l,r] 分成 [l,k] 和 [k+1,r] , 然后用dp[l][k] 和 dp[k+1][r] 推出 dp[l][r]

边界条件: 区间 l==r 时, dp[l][r] 可以从 a[l] 得出(或者为初值)

区间dp的枚举顺序往往很有趣. 根据dp顺序的原则, 执行赋值时等号右边的dp值一定要是已经算出来了的结果. 所以如果只是简单地从 1~n 分别枚举 l , r , k 就会出错, 这里给出两种常用的枚举方法:

1. 首先枚举区间长度 len : 1 ~ n , 然后枚举起点 l : 1 ~ n , 这样可以算出终点 r = l + len -1 , 最后枚举断点 k : l ~ r . 注意终点 r 不能大于序列总长度 n
2. 首先倒序枚举起点 l : n ~ 1 , 然后枚举终点 r : l ~ n , 最后枚举断点 k : l ~ r

如果两种枚举都不喜欢, 那么也可以用记忆化搜索

计数类dp

所谓计数类dp就是常说的统计可行解数目的问题, 区别于求解最优解, 此类问题需要统计所有满足条件的可行解, 而求解最优解的dp问题往往只需要统计子问题时满足不漏的条件即可, 但是计数类dp需要满足不重不漏的条件, 是约束最高的

我们要求解此类问题一个重要的点就是如何划分子问题, 然后做到不重不漏, 大部分情况下我们想到的方法, 同一个解可能会被多次统计, 这是不合理的

数位统计dp

数位是指把一个数字按个、十、百、千等等一位位地拆开, 关注它每一位上的数字. 如果拆的是十进制数, 那么每一位数字都是 0 ~ 9 , 其他进制可类比十进制

数位dp: 用来解决一类特定问题, 这种问题比较好辨认, 一般具有这几个特征:

1. 要求统计满足一定条件的数的数量(即, 最终目的为计数)
2. 这些条件经过转化后可以使用 数位 的思想去理解和判断
3. 输入会提供一个数字区间(有时也只提供上界)来作为统计的限制
4. 上界很大(比如 \(10^{18}\) ), 暴力枚举验证会超时

数位dp的基本原理:

考虑人类计数的方式, 最朴素的计数就是从小到大依次加一. 但我们发现对于位数比较多的数, 这样的过程中有许多重复的部分. 例如, 从 7000 数到 7999 , 从 8000 数到 8999 和从 9000 数到 9999 的过程非常相似, 它们都是后三位从 000 变到 999 , 不一样的地方只有千位这一位, 所以我们可以把这些过程归并起来, 将这些过程中产生的计数答案也都存在一个通用的数组里. 此数组根据题目具体要求设置状态, 用递推或dp的方式进行状态转移

数位dp中通常会利用常规计数的技巧, 比如把一个区间内的答案拆成两部分相减 (即 ans[l,r] = ans[0,r] - ans[0,l-1] )

那么有了通用答案数组, 接下来就是统计答案. 统计答案可以选择记忆化搜索, 也可以选择循环迭代递推. 为了不重不漏地统计所有不超过上限的答案, 要从高到低枚举每一位, 再考虑每一位都可以填哪些数字, 最后利用通用答案数组统计答案

状态压缩dp

dp的时候需要设计状态, 但是有的状态会很复杂. 对于复杂的状态, 也许就不能再像以前那样用一个 i 简单表示. 或许这个状态表示一个有 n (n \(\leqslant\) 16)个元素的集合, 甚至包含了每一个元素的情况. 为了应对这种情况, 我们可以利用状态压缩和位运算, 让一个数字表示一个集合.

状态压缩dp也需要三个步骤:

设计状态: 至少有一维是用一个数字(二进制)表示一个集合

状态转移: 考察每一个决策对集合的影响, 经常使用位运算进行转移

边界条件: 当集合为空或者说只有一个元素之类的

特别注意: 状态压缩是指数级的算法, 所以适合状态压缩的题往往有一个维度的数字很小(比如 n \(\leqslant\) 12 , n \(\leqslant\) 16)

树形dp

设计状态: 至少有一维表示当前正在考虑的树上节点 p

状态转移: 一般使用递归(深搜)由 p 的子节点的dp值得出 p 的dp值

边界条件: 叶子节点没有儿子, 可以只由叶子节点的值得出叶子的dp值