专题进阶 · 动态规划推荐总顺序 · 第 75 / 148 课

按数位构造受上界约束的数字,分清 tight、前导零与性质状态。

先学会这些,再进入本课 记忆化搜索 二维 DP
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 动态规划

数位 DPDigit DP

按数位构造数字,记录是否受上界限制以及所需性质,避免枚举所有整数。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

按数位构造受上界约束的数字,分清 tight、前导零与性质状态。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

统计 0 到 N 中各位数字之和恰好为 S 的整数个数。N 可以很大,不能逐个枚举。

02一步步得到方法

把枚举整数改成枚举位数选择

将 N 写成十进制数字数组。状态 (pos,total,tight) 表示处理到哪一位、已累积的数位和、前缀是否仍与 N 相同。tight=True 时本位最多选 N[pos],否则可选 0..9。

选 d 后,下一个 tight 是 tight and d==limit。只要前面已经严格小于上界,后续再选任何数字都不会超限;不能因为某一位恰好等于上界对应位就重新变成 tight。

前导零是否影响性质

本课允许在所有数字左侧补零到同样位数,数位和不受影响,因此无需额外 started 状态。数字 0 会被全零路径计一次。

若统计实际位数、数字 0 出现次数、相邻位是否相等,就需要 started 区分前导零与真正的数字位,或专门定义零的表示。每增加一种性质,都要判断需要在状态中保存什么信息。

把上界限制沿前缀传播

tight 表示当前前缀是否与上界相同。若已严格更小,后续位可自由取0到9;若仍相同,本位不能超过对应上界数字,且下一状态是否 tight 取决于本位是否相等。

前导零允许统一处理位数较短的数,但若性质涉及数字0出现次数、相邻数字或数的长度,必须加 started 等状态。特别是整数0本身,要单独决定是否计入及怎样表示。

03把一个小例子完全算清楚

N=25,目标数位和 S=3。

步骤计算与状态为什么这样做
十位选 0已小于上界,个位可选 0..9选个位 3,表示数字 3
十位选 1仍小于上界个位选 2,得到 12
十位选 2tight 保持,个位最多 5选 1,得到 21

窄屏可左右滑动表格,阅读完整计算与理由。

满足条件的整数是 3、12、21,共 3 个;前导零不会制造重复数字。

04为什么这个方法成立

  1. 每个 0..N 整数对应唯一的等长补零数字序列。
  2. tight 约束确保构造前缀不超过 N,且所有合法数字选择都被枚举。
  3. 终点仅当数位和等于目标时计 1,缓存合并相同剩余子问题,不改变计数。

05把推导翻译成代码

Python · 可独立运行的教学实现

from functools import cache
def digit_sum_count(n, target):
    if n < 0 or target < 0:
        return 0
    digits = list(map(int,str(n)))
    @cache
    def visit(pos,total,tight):
        if total > target:
            return 0
        if pos == len(digits):
            return int(total == target)
        limit = digits[pos] if tight else 9
        return sum(visit(pos+1,total+d,tight and d==limit)
                   for d in range(limit+1))
    return visit(0,0,True)

逐个理解关键决定

tight and d==limit
只有之前仍贴上界且本位也取上界,下一状态才继续受限。
total > target
数位非负,后续无法把和降回目标,因此可安全剪枝。

06时间、空间与实现范围

位数 D、目标和 S,有 O(D·S) 个主要缓存状态,每个枚举最多 10 个数字;空间 O(D·S) 加递归 O(D)。

大整数计数和字符串位数成本需按实际规模考虑;范围 [L,R] 可用 F(R)−F(L−1)。

07改变条件,检查哪里会出错

把每个补零都算成数字 0 出现

会错误统计较短整数;对这种性质增加 started 状态。

在不同上界之间直接复用依赖上界的缓存

若缓存键未包含上界或相关限制,换查询后可能读到旧结果;应清缓存或设计可复用状态。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

0 到 0,数位和 0 有几个?

需要一点提示

包含数字 0 本身。

查看解析与答案

1 个。

练习 2 · 边界与辨析

统计 10..25 中和为 3 的个数?

需要一点提示

减去 0..9。

查看解析与答案

F(25)−F(9)=3−1=2,对应 12、21。

练习 3 · 变式与迁移

统计不含相邻相同数字需新增什么状态?

需要一点提示

判断当前位需要知道什么过去信息?

查看解析与答案

上一真实数字 last,以及是否已经开始 started;前导零不能当普通前一位。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。