• 当决策集合只增不减时，我们可以用一个变量来维护转移集合的最值，避免多余的枚举。

  • 如果状态中的某些维度可以互相推导，多余的维度可以删去。

  • 有时可以通过额外的算法确定 DP 状态的计算顺序（比如排序）。

  • 有时可以在状态空间中运用等价手法对状态进行缩放。

  • 对于方案计数类的动态规划问题，在设计状态转移方程的决策方式和划分方法时，一个状态的所有决策之间必须具有互斥性，才能保证不会出现重复问题。

  • 单调队列优化的本质是借助单调性，及时排除不可能的决策，保持决策集合的高度有效性和秩序性。

  • 可以用单调队列优化的转移方程一般类似于下面一种形式：fi=min⁡j=liri{fj+cost⁡(i,j)}f_i = \min_{j = l_i}^{r_i}\{f_j + \operatorname{cost}(i, j)\}，其中 cost⁡(i,j)\operatorname{cost}(i, j) 的每一项都只和 ii 或 jj 有关。

  • 倍增优化 DP 求解一般分为两部分：预处理与拼凑。预处理是用“阶段”成倍增长的 DP 计算出若干与 22 的整数次幂相关的代表状态。拼凑是基于“二进制划分”的思想，用上一步得到的代表状态组合成最终的答案。

  • 环形 DP 可以执行两次 DP，第一次把环在任意位置断开进行 DP，第二次将那个位置强行连接进行 DP。

  • 还可以将环拆成链，复制一份接在后面进行 DP，保证不会漏掉可行解。

  • 当计数 DP 算重又不好去重时，不妨增加限制避免重复？