数位统计DP & 状态压缩DP & 树形DP & 记忆化搜索
数位统计DP
- 特点:偏数学
- 要点:分情况讨论
更清析的视频讲解建议移步 $y$ 总提高课数位DP
相应的提高课笔记 数位DP笔记(目前还未整理出来)
AcWing 338. 计数问题
- 实现一个函数
count(n,x)
,统计 $1$ ~ $n$ 中 $x$ 出现的次数[a,b]
中 $x$ 出现的次数为count(b,x) - count(a - 1,x)
- 设 $n=\overline{abcdefg}$ ,分别求出 $1$ 在每一位上出现的次数
- 求 $1$ 在第 $4$ 位上出现的次数,则统计满足 $1\leq \overline{xxx1yyy}\leq \overline{abcdefg}$ 的 $\overline{xxx1yyy}$ 一共有几个
- 当 $000\leq \overline{xxx}\leq \overline{abc} -1$ 时,$\overline{yyy}$ 可取 $000$ ~ $999$ ,共 $\overline{abc} \times 1000$
- 当 $\overline{xxx} =\overline{abc}$
- 当 $d<1$ ,则方案数为 $0$
- 当 $d=1$ ,则 $\overline{yyy}$ 可取 $000$ ~ $efg$ ,方案数为 $\overline{efg} +1$
- 当 $d>1$ ,则 $\overline{yyy}$ 可取 $000$ ~ $999$ ,方案数为 $1000$
- 求其他数字在其他位上出现次数同上
时间复杂度:最坏 $O(n^{2})$
代码
状态压缩DP
把复杂的状态压缩成一个数,比如利用数的二进制表示中隐藏的信息
特点:$n$ 不会很大,因为涉及 $2^{n}$
AcWing 291. 蒙德里安的梦想
- 可以发现,当横向格子确定好之后,剩下的竖向格子只有完全填充这一种摆法,因此只需枚举横向格子
- 动态规划
- 状态表示
f[i,j]
- 集合:所有满足第 $i$ 列有伸出横向格子(意思是 $1\times 2$ 左边的格子在第 $i$ 列)且从上往下摆放的方式与 $j$ 的二进制表示相对应的摆法
- 属性:集合元素数量
- 状态计算
- 转移:
f[i-1,k]
在满足格子不重叠(k&j==0
)和横格之间的连续空格不为奇数(k|j不存在连续奇数个0
)时可以转移到f[i,j]
- 连续空格不为奇数是为了保证竖向格子可以填充
- 方程:
f[i,j]+=f[i-1,k]
- 转移:
- 状态表示
时间复杂度:$O(n\times 2^{n}\times 2^{n})=O(n2^{n})$
代码
AcWing 91. 最短Hamilton路径
- 暴力复杂度:$O(n!\times n)$ 过高
- 动态规划
- 状态表示
f[i,j]
- 集合:从 $0$ 走到
j
,走过的所有点对应i
的二进制表示的所有路径- 二进制每一位,$0$ 表示未走过,$1$ 表示走过
- 属性:集合所有路径的最小值
- 集合:从 $0$ 走到
- 状态计算
- 划分:以倒数第二个点编号来划分
- 方程:倒数第二个点
k
范围从 $0$ 到 $n-1$,则f[i,j] = min(f[i-{j},k] + w[k,j])
- 状态表示
时间复杂度:$O(2^{n}\times n^{2})$
代码
树形DP
AcWing 285. 没有上司的舞会
- 动态规划
- 状态表示
- 集合
f[u,0]
:所有从以 $u$ 为根的子树当中选,并且不选 $u$ 这个点的方案f[u,1]
:所有从以 $u$ 为根的子树当中选,并且选择 $u$ 这个点的方案
- 属性:$Max$
- 集合
- 状态计算
- 递归处理每个子节点 $s_{i}$ 的集合属性
f[u,0]
+= $\sum^{k}_{i=1}$max(f[si][0],f[si][1])
f[u,1]
+= $\sum_{i=1}^{k}$f[si][0]
- 状态表示
时间复杂度:$O(n)$
计算的次数就是每个节点的儿子数,等于树的边数,一共是 $n-1$
代码
记忆化搜索
- 递归写 $dp$ 问题
- 在
dp
函数中,如果某个状态被计算过,就直接返回,否则计算改状态并返回 - 优点:代码复杂度低,思维简单
- 缺点:运行时间比循环稍长,有爆栈的风险
AcWing 901. 滑雪
- 动态规划
- 状态表示
f[i,j]
- 集合:所有从 $(i,j)$ 开始滑的路径
- 属性:$Max$
- 状态计算
- 划分:从 $(i,j)$ 开始往上下左右移动
- 方程:
f[i,j] = max(f[i+1,j],f[i-1,j],f[i,j+1],f[i,j-1]) + 1
- 状态表示