TikTok VO 面试真题解析：不含连续 6 的数字计数（数位 DP）

Problem Description

Input: N (1-20)

Requirement: Count how many numbers with at most N digits do not contain consecutive digit 6s.

Example:

2, 0~99, invalid [66]

这道题的核心是统计“最多 N 位”的所有数字中，有多少个不包含连续两个 6。由于 N 只有 1 到 20，通常可以用数位 DP 来按位枚举：在构造数字时记录前一位是否为 6，并结合“是否受上界约束”进行状态转移，从而高效计算合法数字数量。示例中 N=2 时，范围是 0 到 99，而 66 是唯一需要特别排除的连续 6 组合之一。