第 62 课 - 数位 DP (Digit Dynamic Programming)

所属模块：动态规划 难度：Advanced 标签：digit-dp, count, range, tight

1. 学习目标

• 理解数位 DP 问题的典型特征和应用场景。
• 掌握数位 DP 的核心状态定义方法，特别是“紧贴上界”状态的设计。
• 学会将一个区间 [L, R] 内的计数问题分解为两个前缀计数问题。
• 能够运用深度优先搜索（DFS）结合记忆化（Memoization）实现数位 DP 的核心逻辑。
• 完成 2-3 道经典的数位 DP 练习题。

2. 核心概念

什么是数位 DP？ 数位 DP 是一种用于解决“统计某个区间 [L, R] 内满足特定条件的数字个数”问题的高效动态规划算法。它特别适用于那些条件与数字的每一位（数位）相关的问题。

核心思想： 想象一下你要统计区间 [1, 234] 内所有不含数字 ‘4’ 的数字。暴力枚举每个数字并检查效率很低。数位 DP 的思路是，从数字的最高位（如百位）开始，逐位进行决策（选择 0-9），并在过程中记录一些关键状态。

关键概念 - tight（紧贴上界）： 这是数位 DP 的灵魂状态。当我们从高位到低位构造一个数字时，如果到目前为止构造出的前缀，与数字 N (上界) 的对应前缀完全相同，那么我们在当前位的选择就不能超过 N 在该位的数字。我们就处于 tight = 1 的“紧贴”状态。如果之前某一位我们选择了一个比 N 对应位更小的数字，那么后续所有低位就可以自由选择 0-9，此时我们处于 tight = 0 的“宽松”状态。

状态定义： 一个典型的数位 DP 状态通常包含：

• pos: 当前正在处理第几位（从高到低）。
• tight: 状态标记，表示是否还紧贴着上界 N。
• 其他状态: 根据具体问题而定，比如“已选择的数字之和”、“是否已出现过某个数字”、“前一位是什么”等。

记忆化： 由于不同的路径可能会达到相同的 (pos, tight, 其他状态) 组合，我们可以将这些中间结果缓存起来，避免重复计算，从而将时间复杂度从指数级降低到多项式级。

区间问题处理： 计算 [L, R] 内满足条件的数字个数，等价于计算 [0, R] 的个数减去 [0, L-1] 的个数。因此，我们只需要实现一个函数 count_up_to(N) 来解决从 0 到 N 的计数问题。

3. 代码示例

问题：统计区间 [1, N] 内，不包含数字 '4' 的数字的个数。例如，N=13 时，输出 12 (1,2,3,5,6,7,8,9,10,11,12,13)。

def count_no_four(N):
    """
    统计 [0, N] 中不包含数字 '4' 的数字个数
    """
    if N < 0:
        return 0
    
    # 将数字 N 转换为字符串列表，方便按位处理，例如 N=123 -> ['1', '2', '3']
    s = str(N)
    n = len(s)
    
    # 记忆化缓存: 字典，键为 (pos, tight)，值为当前状态下的方案数
    memo = {}
    
    def dfs(pos, tight):
        """
        pos: 当前处理到第几位 (0-based，从最高位开始)
        tight: 是否还紧贴上界 (1 紧贴, 0 宽松)
        返回: 从当前状态开始，能够构造出的合法数字的个数
        """
        # 递归出口：已经处理完所有位，说明找到了一个合法数字
        if pos == n:
            return 1
        
        # 检查记忆化缓存
        if (pos, tight) in memo:
            return memo[(pos, tight)]
        
        res = 0
        # 确定当前位所能选择的数字上限
        up = int(s[pos]) if tight else 9
        
        # 枚举当前位可以选择的数字 d (从 0 到 up)
        for d in range(up + 1):
            # 如果当前位选择了 '4'，则跳过，该分支不合法
            if d == 4:
                continue
            # 计算下一状态：如果当前还紧贴，并且选择了上限值 up，则下一状态仍紧贴，否则宽松
            new_tight = tight and (d == up)
            res += dfs(pos + 1, new_tight)
        
        # 将结果存入缓存
        memo[(pos, tight)] = res
        return res
    
    # 从第0位（最高位）开始，初始状态是紧贴的
    # 注意：这个函数统计的是 [0, N]，包括 0。但 0 通常不包含数字 4，是合法的。
    # 如果题目要求统计 [1, N]，可以最后减去 0 的情况（如果 0 不算的话），或者稍作调整。
    return dfs(0, True)

# 包装函数，统计 [a, b] 闭区间
def solve(a, b):
    # count_up_to(b) 统计 [0, b]，count_up_to(a-1) 统计 [0, a-1]
    # 两者相减即得 [a, b] 的个数
    return count_no_four(b) - count_no_four(a - 1)

# 测试
if __name__ == "__main__":
    # 测试 [1, 13]
    print(solve(1, 13))  # 输出: 12
    # 测试 [1, 100]
    print(solve(1, 100)) # 输出: 81 (100 以内共100个数，去掉10, 20, 30, 40, 41, ..., 49, 50, ..., 90, 100 中的含4的)

4. 实践练习

练习 1 (基础) 修改上面的代码，统计区间 [1, N] 内，不包含数字 ‘62’ 的数字个数。提示：需要增加一个状态来记录前一位是否是 ‘6’。

练习 2 (中等) 统计区间 [1, N] 内，数字各位之和为奇数 的数字个数。提示：状态需要记录当前的数字和，或者更高效地，记录当前数字和的奇偶性。

练习 3 (挑战) 统计区间 [1, N] 内，不含连续两个 ‘1’ 的数字个数（例如，11, 110, 1011 不合法，但 101, 112 合法）。提示：状态需要记录前一位是否是 ‘1’。

5. 常见错误

1. 状态定义不全：忘记记录 tight 状态，或者在需要记录前几位信息（如前一位数字、是否已用过某个数字等）时遗漏，导致记忆化失效或结果错误。
2. 前导零处理不当：在上述通用框架中，数字前导的零是被允许的（例如，统计 000123 等同于 123）。但有时题目会特别说明“不含前导零”。这时需要增加一个状态 lead 来标记当前是否还在前导零部分，并做相应处理。
3. 记忆化条件错误：记忆化的键（Key）必须包含所有会影响后续决策的状态变量。如果遗漏了某个状态（比如 tight），会导致错误的结果被缓存和复用。
4. 区间计算时边界错误：计算 [L, R] 时，应该是 count(R) - count(L-1)。如果 L=1，且 count(0) 返回的是包含 0 的计数（通常为1），那么 count(1-1) = count(0) 可能多算了 0 这个数。需要根据题意明确 0 是否算在解内，并调整 count 函数的定义。

6. 小结

• 数位 DP 是什么：一种解决与数字位数相关的区间计数问题的高效算法。
• 核心状态：pos（当前处理位数）和 tight（是否紧贴上界）是通用状态。根据问题添加其他必要状态。
• 实现方法：使用深度优先搜索（DFS）从高位向低位进行决策，并利用记忆化（Memoization）缓存中间结果。
• 区间求解：将 [L, R] 问题分解为两个前缀问题 count(R) - count(L-1)。
• 关键技巧：将数字转化为字符串，以便按位处理；在循环中枚举当前位可能的选择，并根据 tight 确定枚举上限。

数位 DP 的难点在于状态设计，理解了 tight 状态的精髓后，你就能将各种数位约束问题建模为动态规划问题。多练习不同类型的题目是掌握它的不二法门。