数位 DP

动态规划 · HTML

数学 / 逻辑形态

solve(pos,tight,started,summary) 返回从当前位置填完的方案数。digit 范围 0..limit，其中 limit=tight?digits[pos]:base-1；next_tight=tight and digit==limit_digit。区间 [L,R] 用 F(R)-F(L-1)。

识别信号

• 要求统计 [0,N] 或 [L,R] 内整数。
• 性质可逐位更新，如数位和、余数、出现次数或相邻约束。
• N 很大，逐数枚举不可行。
• 大量数共享相同高位前缀状态。
• 上界限制可由 tight 标志表达。

容易误判的相似信号

核心不变量

memo 状态代表所有具有同一 pos/tight/started/summary 的前缀，它们的合法后缀集合完全相同；tight 准确记录是否仍贴住上界前缀。

状态、转移与处理顺序

Python 骨架

from functools import lru_cache

def count_digit_sum_at_most(n, target):
    if n < 0: return 0
    digits = list(map(int, str(n)))
    @lru_cache(None)
    def dfs(pos, tight, total):
        if total > target: return 0
        if pos == len(digits): return int(total == target)
        limit = digits[pos] if tight else 9
        ans = 0
        for d in range(limit + 1):
            ans += dfs(pos + 1, tight and d == limit, total + d)
        return ans
    return dfs(0, True, 0)

正确性思路

1. 每个 0..N 的定长补零表示对应唯一数位选择路径。
2. tight 规则恰好排除首个超过上界的前缀，保留所有不超过上界的路径。
3. summary 按位更新且终点只接受目标性质；互异路径对应互异整数，计数无重漏。

复杂度

边界条件

• n<0 用于 L-1
• 数字 0 是否计入
• 前导零与 started
• 上界本身
• summary 剪枝
• 不同进制

错误模式

选择与排除规则

• 先把区间查询化为前缀计数 F(N)。
• 证明性质能由小 summary 逐位更新。
• 明确前导零是否属于数字表示。
• 用 brute force 小 N 对拍边界。

相关模板

原创微型例子

Recall prompts

• tight 的精确定义是什么？
• 什么时候必须加入 started？
• [L,R] 如何统一成两个 F 调用？

我的补充