[!info] related notes 动态规划

数位 DP

一句话

把一个数字拆成十进制位，从高位到低位枚举，在“是否受上界限制”的条件下统计满足条件的数字个数。

识别信号

• 求区间 [0, n] 或 [l, r] 里有多少个数满足某种数位条件
• 条件和“每一位”有关，比如：
  • 不含某个数字
  • 数位和为多少
  • 邻位关系限制

常见状态

dfs(pos, limit, started, state)

• pos：当前处理到第几位
• limit：这一位是否受上界约束
• started：前面是否已经填过非前导零
• state：题目附加状态（数位和、前一位、出现次数等）

为什么常写成记忆化搜索

数位 DP 更自然的写法通常是递归：

• 枚举当前位填什么
• 把限制和状态传给下一位

只有在 limit = false 且 started 等条件稳定时，才缓存答案。

通用模板

function dfs(pos, limit, started, state) {
    if (pos === digits.length) {
        return ...;
    }

    if (!limit && memo.has(key)) return memo.get(key);

    const up = limit ? digits[pos] : 9;
    let ans = 0;

    for (let d = 0; d <= up; d++) {
        ans += dfs(pos + 1, limit && d === up, started || d !== 0, nextState);
    }

    if (!limit) memo.set(key, ans);
    return ans;
}

高频坑

• 把前导零当成正常数字参与限制
• limit 为真时错误地缓存，导致状态污染
• 求区间 [l, r] 时忘了转成 solve(r) - solve(l - 1)