跳到主要内容

数位动态规划

本节目标

按数位前缀统计不超过上界的整数。

识别信号​

问题要求统计区间内满足数位限制的整数，且限制由已经确定的前缀决定。

状态定义与转移推导​

position 表示当前位，tight 表示是否仍贴着上界；需要忽略前导零时加 started，需要去重时加 mask。

初始化与遍历顺序​

先把 F(x) 写成从高位到低位的递归，区间答案为 F(right)-F(left-1)；非紧状态可记忆化。

通用模板​

dfs(pos, tight, started, state):
  enumerate digit <= upper
  update state only after number starts

空间优化与复杂度​

状态数是位数、上界标记和附加状态的乘积；仅缓存 tight=false 的状态即可。

母题序列​

  1. 度的数量（拓展）：限制每位只能是 0 或 1。
  2. 统计特殊整数（拓展）：用掩码禁止重复数字。

常见误区​

把一般非零位也当作 1、把前导零写入掩码，或直接枚举整个区间。

迁移方向​

本章止于 tight、started 和集合掩码；不扩展到数位自动机。