这道题是今天刚出炉的 TikTok 一面算法题，整体难度不高，但如果没有 DP 建模经验，很容易在 10 分钟内卡死。

题目本身不复杂：

输入一个整数 N（1 到 20），统计所有不超过 N 位的数字中，不包含连续 “6” 的个数。

面试官一开始没有写在屏幕上，而是直接口述，然后很自然地补了一个例子：

“比如 N = 2，就是 0 到 99，一共 100 个数，其中 66 不合法，所以答案是 99。”

这里其实是在确认你有没有理解清楚两件事：

第一，是“不超过 N 位”，不是刚好 N 位
第二，是“只要出现连续 6 就不合法”，单个 6 是允许的

候选人当时没有犹豫太久，很快给了一个方向：

“我感觉可以用 DP，从低位往高位构造。”

这一步是关键，如果这里没想到 DP，后面基本就会走偏。

思路是怎么一步步走出来的？

面试中最常见的错误，其实是直接想着：

“我能不能枚举 0 到 10^N - 1，然后判断？”

理论上可以，但 N 最大是 20，这意味着最多是 10^20 个数，直接爆炸。

所以必须换一个角度——不要枚举数字，而是“构造数字”。

当你开始“构造”一个数字的时候，就会发现问题变得很清晰：

我们是从左到右一位一位填数字，每一位都有 0~9 的选择。

但唯一的限制是：

👉 不能出现两个连续的 6

于是面试官在这里会轻轻往前推一句：

“那你在构造的时候，需要记录什么信息？”

这句话其实就是在引导你设计状态。

关键突破点：只需要记住“上一位是不是 6”

很多人会在这里想复杂，比如记录整个字符串，或者记录出现过几个 6，其实完全没必要。

你只需要关心一件事：

👉 当前这一位，前一位是不是 6？

于是状态就自然出来了：

• 如果当前数字最后一位不是 6
• 如果当前数字最后一位是 6

候选人当时就是在这里稍微卡了一下，用语言描述了一段时间，面试官也提示了一句：

“你可以把状态拆开写一下。”

一旦写出来，就变得非常清晰：

• dp[i][0]：长度为 i，最后一位不是 6
• dp[i][1]：长度为 i，最后一位是 6

转移是怎么想出来的？

这一步其实是面试最核心的地方。

你可以想象你现在已经有了长度为 i-1 的所有合法数字，现在要在后面再加一位。

如果你这一位打算填“不是 6”：

那前一位是什么都无所谓，因为不会形成连续 6。

而“不是 6”的数字一共有 9 个（0~9 去掉 6）。

面试过程中一个很真实的小细节

候选人写到这里的时候，突然停了一下，说了一句：

“如果 N 很大，这个数可能会 overflow，我要用 long。”

这个点其实挺加分的。

因为很多人只顾着写 DP，完全没意识到：

👉 10^20 这个级别，int 肯定不够

最后结果是怎么得到的？

当你把长度为 N 的所有情况算出来之后：

只需要把“最后一位是 6”和“不是 6”的情况加起来就行。

也就是：

👉 所有合法的 N 位数字数量

（而题目中的“0 到 99 / 999”这种，其实天然就包含在 DP 里了，不需要额外处理）

这道题为什么容易挂？

看起来很简单，但实际面试中有三个典型翻车点：

第一个，是没想到用 DP，还在想着暴力或回溯
第二个，是状态设计不对，比如想记录整个字符串
第三个，是转移写错，尤其是 dp[i][0] 那一行

还有一个更隐蔽的问题是：

很多人会误以为“不能包含 6”，而不是“不能连续 6”。

如果面试官继续追问，会发生什么？

TikTok 这类题，通常不会停在这里。

更常见的情况是，面试官会往下改一改题：

“如果不允许出现 ‘666’ 呢？”

或者：

“如果我给你一个区间 [L, R] 呢？”

这时候就不再是简单 DP，而是直接升级成：

👉 数位 DP（Digit DP）

如果你前面只是“会写代码”，但没有真正理解状态，那这里基本就顶不住了。

最后总结一句话

这道题的本质其实非常简单：

👉 只要问题涉及“不能出现某种连续模式”，第一反应就是状态机 + DP

如果你近期准备 TikTok / Meta / Google / Stripe 等公司面试，可以提前准备这些高频题目。

往往一两道题就决定了面试结果。

如果你最近有 VO 面试，提前准备这些 真实题型和思路，会非常关键。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~