一些 dp 状态 & 技巧

发布于 2023-04-14 | 标签: DP 、小技巧、学习笔记 | 3分钟 | 446字数

设 $f_x$ 表示达到状态 $x$ 的期望，答案即为 $f_{need}$ ；
设 $f_{x,y}$ 表示从状态 $x$ 转到状态 $y$ 的期望，求答案的时候加起来；
遇到求 $()^x$ 的时候直接二项式定理设多个 dp 数组，或者考虑 $x$ 个人同时进行一样的操作；
考虑折线图/笛卡尔树；
箭头 dp：

设 $dp_{i,j}$ 表示前 $i$ 个元素，有 $j$ 段。转移考虑新建段、加入某段的左边/右边、合并两段。

例题：
非负整数划分 dp：

非负整数 $n$ 划分成 $m$ 个带标号非负整数的方案数。

设 $f_{i,j}$ 表示 $j$ 划分成 $i$ 个带标号非负整数的方案数，那么有 $f_{*,0}=1$ 。转移考虑有多少个 $\ge 1$ 的数：
$f_{i,j}=\sum\limits_{k=1}^{\min(i,j)}\binom{i}{k}f_{k,j-k}$
折线优化：

考虑某些形如 $f_{i,j}=\max(f_{i-1,j+x}+w_1,f_{i-1,j+y}+w_2)$ 这样的只和上一列有关的 dp，可以猜想并且经常有：

存在某个 $k$ 满足 $f_{i,j}=\begin{cases}f_{i-1,j+x}+w_1&j\le k\\f_{i-1,j+y}+w_2&j>k\end{cases}$

例题：
在 dfs 序上 dp：【2025NOI模拟赛19】b酱的果子