从暴力枚举到数字DP：彻底讲清“包含数字9的数”

我们去翻任何一个入门编程练习集，大概率会看到这样一道题，标题就叫"包含数字9的数"，前面往往还挂着一个序号"1."。它通常跟在"打印Hello World"后面，题目描述很简单：从1到100（升级版是1到N）找出所有包含数字9的数，输出它们，再统计个数。很多同学扫一眼就开始写循环，以为这是送分题，结果交上去之后在边界测试上栽了跟头。

这道题我见到的次数非常多：C语言课后的第一道上手题、某个入门算法题库的第1题、甚至面试热身时被拿来当"开口题"。它看着平平无奇，实际上一道题能拆出三个层次：暴力枚举、数学计数、数字DP。第三个层次甚至能通到不少笔试里的大数位统计题。这篇文章就把从第一层到第三层的完整思路、代码和踩坑记录一次讲清楚。适合正在刷题入门的新手，也适合想搞明白"这类题还能怎么优化"的进阶读者。代码用C++和Python混着写，核心是思路，语言只是工具。

1. 先看清楚这道题考的是什么

1.1 题目到底让你做什么

先还原一下最常见的题目原文：在1到100之间，找出所有含有数字9的数，并把它们全部输出，最后输出总数。有些版本把100改成用户输入的N，有些版本反过来问"不含数字9的数有多少个"，本质上是同一个问题的两个面。

这里的关键并不是"会不会写循环"，而是能不能把一个整数正确地拆成单个数字，或者正确地用字符串判断子串。你可以用取余和整除拆位，也可以用语言自带的字符串函数查找。两种方式都能得到正确答案，但它们暴露的思路不一样：前者考验你对整数运算的理解，后者考验你对API的熟悉程度。

更重要的是，这道题天然地引出了"暴力解法够不够用"的问题。N是100的时候，怎么写都行；N是10^9的时候，暴力枚举跑一年都跑不完。这时候你就要想，有没有办法不一个一个数，直接"算"出结果来。这个从蛮力到公式、再到动态规划的递进，才是这道题真正的价值所在。

1.2 三个层级的解法地图

我习惯把这道题的解法分成三个层级，对应三种典型的编程思维阶段：

• 第一层：暴力枚举。写一个循环，逐个判断每个数字里有没有9。代码简单，适合小范围，也适合用来验证其他解法对不对。
• 第二层：数学计数。找到"补位""排列组合"的规律，用公式直接算出结果。不需要循环遍历，适合N在10^9以内、对性能有要求的场景。
• 第三层：数字DP。把"数位填数字"建模成状态转移，用记忆化搜索统一解决。不仅适用任意大N，还能扩展到"至少出现两次9""同时含9和8""求和""求第K个"等一系列变形。

在往下讲之前，先定一个可验证的小目标。我手动列出1到100之间所有含9的数：9，19，29，39，49，59，69，79，89，90，91，92，93，94，95，96，97，98，99，一共19个。注意99这个数出现了两个9，但统计"个数"时只能算一个数。后面不管你写哪种解法，第一件事就是用这组基准数据验证，输出不是19就是错的。

2. 暴力枚举：两种快速出结果的写法

2.1 字符串判断法

第一种思路非常直接，把每个数字转成字符串，看里面有没有字符'9'。C++代码可以这么写：

#include <iostream> #include <string> using namespace std; int main() { int n = 100; int cnt = 0; for (int i = 1; i <= n; i++) { string s = to_string(i); if (s.find('9') != string::npos) { cout << i << " "; cnt++; } } cout << "\ncount = " << cnt << endl; return 0; }

Python版本更短，几乎是自然语言：

n = 100 nums = [i for i in range(1, n + 1) if '9' in str(i)] print(nums) print(f"count = {len(nums)}")

这种写法的优势是几乎不会出错。字符串查找是现成功能，不需要自己操心取余、整除这些细节。新手用它快速验证答案是19，完全没有问题。

但它有两个不能忽视的缺点。第一，每次循环都要做一次整数到字符串的转换，这个操作的开销比纯算术运算大得多，N一大了性能很难看。第二，它本质上回避了"拆位"这个核心考点。如果题目明确考你的就是"会不会用运算符拆数字"，字符串法虽然能过，但你练不到点上。我的建议是：当作验证手段可以，当作正式解法别依赖。

提示：在部分老旧编译环境里to_string不可用，或者需要特殊配置才能编译。如果你在某个在线练习系统上做题，尽量把编译标准切到新版本，或者直接改用下面的取余法。

2.2 逐位取余法

第二种思路不碰字符串，用整除和取余把数字的每一位拆出来，这也是C语言教材里最经典的写法：

#include <iostream> using namespace std; bool hasDigit9(int x) { while (x > 0) { if (x % 10 == 9) return true; x /= 10; } return false; } int main() { int n = 100, cnt = 0; for (int i = 1; i <= n; i++) { if (hasDigit9(i)) { cout << i << " "; cnt++; } } cout << "\ncount = " << cnt << endl; return 0; }

hasDigit9是核心函数。每次循环做两件事：x % 10取当前最低位，如果等于9直接返回true；然后x /= 10把最低位丢掉。拿x=97举例：第一次循环，97%10=7不是9，x变成9；第二次循环，9%10=9，命中，返回true。

这里有两个细节值得说。一是"提前返回"很重要，一旦发现某一位是9，立刻结束循环，后面的位不用再拆，这在遍历大量数字时能省不少时间。二是循环条件写成x > 0，注意x=0时循环体不执行，hasDigit9(0)返回false，这个语义是对的，因为0确实不含9。

2.3 暴力法的性能边界在哪里

这两种暴力写法在N等于100、1000、10000的时候都是瞬间出结果。但你真把N改成100000000（10^8）试试：C++纯取余要好几秒，Python字符串法可能要几十秒，在任何在线评测系统里基本都是超时重灾区。

原因不复杂，10^8个数，平均每个数要拆大约8位，总操作量接近8亿次取余和整除，单线程下已经逼近秒级到十秒级的界线。所以我一般用这样一个粗略判断标准：

• N ≤ 10^6：暴力随便写；
• N ≤ 10^7：C++优化后勉强能跑，Python很悬；
• N ≥ 10^8：老老实实转数学计数或数字DP。

暴力法不是没用，它是你的"基准答案生成器"。后面任何高级算法写出来，先拿小N的结果和暴力结果对拍，这是最让人放心的验证方式。

3. 数学计数法：找到规律就能省略循环

3.1 从0-99入手：补位思维

暴力写多了，你会发现结果是有规律的。1到99之间含9的数有19个，为什么是19？

把0到99看成"00、01、02……99"这种补位后的两位数，每一位都能取0到9。那么不含数字9的数怎么算？每一位只能取0到8这9种选择，所以一共9×9=81个。总共100个数，含9的就是100-81=19个。

这个思路的核心是"补位"。高位的0不是没有意义的符号，它占了一个可选位置，参与排列组合计算。所以不能把一位数、两位数分开数，而要统一补成固定长度再整体计算。这也是后面所有数位统计技巧的地基。

3.2 任意整段范围的通式

补位思路能直接推广。0到999（看成000到999），每一位有9种不含9的选择，所以不含9的数有9^3=729个，总数1000个，含9的就是1000-729=271个。

推广到k位数：从0到10^k-1，含9的数的个数是10^k - 9^k。验证一下：k=1时，0到9之间含9的只有9这个数，10^1-9^1=1，对；k=2时19，对；k=3时271，对。

到这里你可能会想，那N=123这种不是整十整百的数怎么办？不能直接套通式，因为123不是10的整次幂减1。这就到了下一节的内容。

3.3 手算N=123：区间拆分与按位容斥

以N=123为例，我手写一遍计算过程，感受一下思路。

方法一：按区间拆。把1到123分成1到99和100到123两段。1到99含9的个数是19。100到123这段，百位固定是1，后两位从00到23，这里面含9的数只有109和119两个。总数就是19+2=21。

方法二：按数字9出现的位置拆，再用容斥去重。9出现在个位的数：个位是9，每隔10个出现一次，1到123中个位为9的有9、19、……、119，一共12个。9出现在十位的数：十位是9的是90到99，一共10个，190到199已经超范围了。但是注意，99这个数同时满足"个位是9"和"十位是9"，在前面两类里各被算了一次，要减掉一次。所以总数是12+10-1=21。

两种方法结果一致。第一种直观，第二种更系统，适合推广到更大范围。不过说句实话，当N的位数变多，容斥的项会成倍增加，手工算很容易漏。真正可复现的通用写法，我等一下在数字DP那一节给你。

3.4 一个公式陷阱：数次数和数个数是两回事

在网上搜"1到N中数字9出现次数"，你会找到一个非常经典的通项模板，按每一位拆higher、cur、lower三部分累加。有些同学拿过来改一改，直接用在"包含数字9的数"这道题上，然后翻车了。

看这段代码：

long long countDigit9Occurrence(long long N) { long long total = 0; for (long long pow10 = 1; pow10 <= N; pow10 *= 10) { long long higher = N / (pow10 * 10); long long cur = (N / pow10) % 10; long long lower = N % pow10; if (cur < 9) { total += higher * pow10; } else if (cur == 9) { total += higher * pow10 + lower + 1; } else { total += (higher + 1) * pow10; } } return total; }

它计算的是"数字9这个字符在0到N中一共出现了多少次"，而不是"有多少个数包含9"。这两者差在哪？差在99这种双9数上。按次数算，99贡献了2；按个数算，99只算1。所以拿N=123测试，这个函数返回22，而正确答案是21。拿N=99测试，它返回20，正确答案是19。

这个区别特别容易踩，因为结果很接近，你不仔细对拍根本发现不了。记住一个判断标准：题目说"包含9的数"或"含有9的数字"，统计的是个数，每个数最多贡献1；题目说"9出现的次数"或"9出现的频次"，统计的是次数，一个数可以贡献多次。两个模板不能混用。

如果你就是想用一个不用DP的数学方法统计"个数"，最顺的思路是补集：总数减掉"不含9的数的个数"。从0到N一共N+1个数，0本身不含9，所以含9的个数就是(N+1)减去不含9的个数。而不含9的个数可以用逐位组合的方式算，本质上是把0到N范围内每一位都限定在0到8之间，统计满足条件的数字个数。

4. 数字DP解法：面对超大N的通用方案

4.1 状态设计：pos、tight、hasNine

数字DP是这类"统计1到N之间满足某条件的数字个数"问题的标准解法。它把构造一个数字的过程，拆成从高位到低位一位一位填数字的过程，用记忆化搜索把重复子问题缓存起来。

我先解释一个关键概念：tight（是否贴着上界）。假设N=123，当我们从百位开始填数字时，百位最大只能填1，因为填2就超过123了。这个"最大只能填N的这一位"的状态就叫tight。一旦某个位置填了比N对应位更小的数字，比如百位填了0，那么后面的十位、个位就自由了，想填什么填什么，最大都是9；如果一直贴着N填，每一位都被限制在N的对应位上。

对于"包含数字9"这个条件，我们还需要一个状态hasNine，记录到目前为止填过的数字里有没有出现过9。最后统计的时候，只有hasNine为true的完整数字才计入答案。

所以状态是三维的：pos表示当前填到第几位（或者还剩几位），tight表示是否贴上界，hasNine表示是否已经出现过9。用数组dp[pos][tight][hasNine]做记忆化。

4.2 记忆化搜索完整代码

C++实现：

#include <bits/stdc++.h> using namespace std; string s; long long dp[20][2][2]; long long dfs(int pos, int tight, int hasNine) { if (pos == (int)s.size()) { return hasNine ? 1 : 0; } long long &ans = dp[pos][tight][hasNine]; if (ans != -1) return ans; ans = 0; int limit = tight ? (s[pos] - '0') : 9; for (int d = 0; d <= limit; d++) { ans += dfs(pos + 1, tight && (d == limit), hasNine || (d == 9)); } return ans; } long long countWith9(long long N) { s = to_string(N); memset(dp, -1, sizeof(dp)); return dfs(0, 1, 0); } int main() { cout << countWith9(100) << endl; // 19 cout << countWith9(123) << endl; // 21 cout << countWith9(999) << endl; // 271 cout << countWith9(1000000000LL) << endl; // 612579511 return 0; }

Python版本：

from functools import lru_cache def count_with_9(n): s = str(n) @lru_cache(None) def dfs(pos, tight, has_nine): if pos == len(s): return 1 if has_nine else 0 limit = int(s[pos]) if tight else 9 total = 0 for d in range(limit + 1): total += dfs(pos + 1, tight and d == limit, has_nine or d == 9) return total return dfs(0, True, False) print(count_with_9(100)) print(count_with_9(123)) print(count_with_9(999)) print(count_with_9(10**9))

我建议你仔细读dfs里的逻辑：limit决定当前位置能填的最大数字；for循环枚举当前位填0到limit；tight && (d == limit)表示只有"之前贴着上界、并且这一位也填到了上限"时，下一位才继续贴着；hasNine || (d == 9)表示只要之前出现过9或者这一位填了9，就标记为"已出现过9"。

这里有一个值得注意的细节：数字前导0不需要特殊处理。因为前导0不会让hasNine变成true，它只是占位。数字9在DP里被表示成"若干前导0加一个9"，恰好能算进hasNine为true的情况；数字0被表示成"全是0"，hasNine为false，不会误计。所以状态里不需要额外维护"是否已经填过非零数字"这类标志。

4.3 验证输出与复杂度分析

上面代码的输出，我直接告诉你：countWith9(100)是19，countWith9(123)是21，countWith9(999)是271，countWith9(10^9)是612579511。你可以拿第3节的数学结论对一下，前三个完全吻合。第四个用暴力根本跑不动，但DP毫秒级出结果。

复杂度方面，状态数大概是pos维度（最多19位）乘以tight（2种）乘以hasNine（2种），每个状态里枚举0到9共10个数字，所以总运算量大概19×2×2×10=760次级别的常数，跟N的大小没有直接关系。这就是为什么它能处理N=10^18这种天文数字。

dp数组第一维开20就够了。long long能表示到约9.2×10^18，也就是19位数，开20个位置是安全的。如果你用int，N一大直接溢出，这是非常隐蔽的坑。

5. 常见错误与排错实录

5.1 新手最容易犯的五个错

我在这里把这几年见到的典型错误集中整理一下，每一个都是真实发生过的：

第一个，99重复计数。很多人判断条件写成两个独立的if：if (i % 10 == 9) cnt++; if (i / 10 == 9) cnt++;，在99这里触发两次，结果多算一个。正确做法是用或逻辑，或者一旦检测到9就跳过剩下的判断。

第二个，漏掉90到99这一段。只判断了个位是不是9，忘了十位也有可能是9。其实只要用完整的"逐位取余"循环，每一位都检查一遍，这个问题就不会出现。

第三个，取余循环忘了除10。代码写成while (x > 0) { if (x % 10 == 9) ... }但没写x /= 10，结果死循环。这个错误看起来低级，但紧张的时候真的会犯。

第四个，边界漏算。N=9时结果应该是1，有人从0开始循环却不小心把0也算进去；N=99时结果应该是19，有人只算到98，把99漏了。写循环时一定要确认起点和终点是否包含边界值。

第五个，把"出现次数"和"含9个数"混用。这个我上一节详细讲过了，典型表现是99这种数贡献了2，导致结果系统性偏大。这种错误最阴险，因为小范围测试时往往能通过几个用例，只有对拍才暴露。

5.2 一套标准测试用例自查表

我给自己定了一套基准用例，任何解法写完先跑这个表：

这几个用例覆盖了单边界、双9、整段、非整段、进位多种情况，任何一个能蒙混过关都不容易。特别是99和123这两个，基本能秒杀所有有逻辑缺陷的解法。

5.3 一次真实的排错过程

情景回放：一位同学写了段代码，测N=100输出20，比正确答案19多1，他改了很久没找到问题。我让他把含有9的数字打印出来，他在输出列表里看到99出现了两次。

再看他的判断逻辑：if (i % 10 == 9) { cout << i << endl; cnt++; } if (i / 10 % 10 == 9) { cout << i << endl; cnt++; }。这段代码对99会先因为个位是9输出一次，再因为十位是9输出一次，所以列表里99出现两次，计数多1。

我当时给的修改建议有两个：最简单的，把两个if改成if ((i % 10 == 9) || (i / 10 % 10 == 9))，让99只触发一次；或者更彻底一点，改成逐位循环，一旦检测到9就break。从这以后我就形成了一个习惯：但凡是统计"包含某数字的数的个数"，第一反应一定是"提前返回"而不是"逐条件累加"，因为累加天然会造成重复。

6. 从这道题延伸出去：变形与升级

6.1 求包含9的数字之和

第一道变形题：不只统计个数，还要把所有含9的数字加起来。N小的时候，暴力循环顺便求和就行。N大的时候，要在数字DP里多维护一个"和"的状态。

思路是这样的：dfs不但返回满足条件的数字个数，还返回它们的和。转移的时候，如果当前位填d，并且后面有k个完整数字满足条件，那么d这个位对最终答案的贡献是d × 10^(剩余位数) × k，再加上所有后序数字本身的和。实现上可以用一个pair返回(count, sum)，递归的时候分层累加。

这个变形的价值在于，它告诉你数字DP的状态不只可以维护"是否满足某条件"这种布尔量，还可以维护"和""乘积""最大值"等更丰富的统计量，只要这些量能在状态转移时正确合并。

6.2 求第K个包含9的数字

第二道变形题：给定K，求第K个包含9的数字，K可能非常大。比如第1个是9，第10个是89，第19个是99，第20个是109。

解法非常优雅：二分答案。因为countWith9(mid)是一个随mid增大单调不减的函数，所以可以二分搜索最小的mid，使得countWith9(mid)大于等于K。二分的上界设一个足够大的值，比如10^18，然后跑大概60次二分，每次调用countWith9的代价是常数级的，所以整体非常快。

模板长这样：

long long kthWith9(long long k) { long long lo = 9, hi = 1000000000000000000LL; while (lo < hi) { long long mid = lo + (hi - lo) / 2; if (countWith9(mid) >= k) hi = mid; else lo = mid + 1; } return lo; }

这个"二分+计数函数"的组合是很多竞赛题的通用套路，凡是统计函数单调，都能用它求第K个满足条件的对象。

6.3 禁位数字问题的通用套路

第三类变形是把"包含9"换成其他条件。比如"统计1到N中各位都不含数字3的数""统计1到N中至少出现两次9的数""统计1到N中同时包含8和9的数"。其实都是同一个套路。

• "不含某个数字"：数字DP的状态不需要has标志，反而是逐位枚举时直接跳过那个数字，或者用组合公式算。
• "至少出现两次9"：把hasNine从布尔值扩展成"出现9的次数"的计数，0次、1次、2次及以上，三种状态。
• "同时含8和9"：两个布尔标志位，hasEight和hasNine，最后统计两个都为true的情况。

你只要掌握"贴着上界向下填数"的状态设计思路，这些变形本质上是往状态里加维度。从这道只有20行的DP题开始，你就能通吃一大类数位统计问题，这笔账还是挺划算的。

7. 几个做题之外的实在建议

最后聊几句代码之外的东西。我自己的习惯是，任何一个计数类题目，写正式解法之前一定先手动列一个小范围基准表。像这道题的1到100，我宁愿花两分钟手数一遍，也不愿意拿一个可能写错的程序去"验证"另一个也可能写错的程序。有了基准数据，对拍才有意义。

还有一点，就是不要小看暴力解法。很多人一上来就背数字DP模板，结果在面试时被追问"你的DP状态为什么这样设计"就答不上来。我的建议是，先写暴力，再推导数学规律，最后才上DP。每一步都理解"为什么之前的解法不行、新的解法好在哪"，这样学到的东西才是自己的。这道题我前前后后带了很多人做过，凡是老老实实从暴力开始推的，后面遇到"统计第K个不含某数字的数"这类进阶题，基本都能自己写出来；凡是直接抄模板的，换个条件就卡住。差别不在于智商，在于有没有真的理解状态转移的含义。