1. 从一道蓝桥杯国赛真题说起二进制问题的“陷阱”去年带学生备赛蓝桥杯国赛碰到一道关于二进制数的题目卡住了不少人。题目大意是给定一个区间[L, R]问在这个区间内有多少个整数的二进制表示中1的个数是质数。比如数字5的二进制是101有2个1而2是质数所以它符合条件。乍一看这题似乎不难。很多同学的第一反应是写个循环从L遍历到R对每个数用__builtin_popcountGCC内置函数或者自己写个位运算统计1的个数再判断是不是质数最后累加。这个思路清晰直接对于小范围的L, R完全可行。但问题就出在数据范围上——国赛的题目L和R的取值动辄就是1到10^18这个量级。你算算10^18次循环就算每次操作都是纳秒级也得跑上几十年。暴力枚举的路从起点就被堵死了。这就是典型的“数位统计”问题。它的核心矛盾在于数值范围巨大无法逐个枚举但数字的每一位在二进制下就是每一个 bit的取值是有限的0 或 1。我们需要一种方法能够不依赖具体的数字而是基于“数位”的结构来进行高效计数。数位DPDigit Dynamic Programming正是为此而生的利器。它把一个大问题分解为对数字每一位的、带有状态记忆的搜索或递推将指数级复杂度降到了多项式级。今天我就结合这道蓝桥杯国赛真题把数位DP的两种核心实现思路——记忆化搜索和递推——掰开揉碎了讲清楚。你会发现它不仅是解决这道题的关键更是处理一大类“数字区间内满足某种位数性质”问题的通用框架。2. 数位DP的核心思想化整为零与状态压缩在深入代码之前我们必须先建立起对“数位DP到底在干什么”的直观理解。想象一下我们要统计1到12345之间所有满足条件的数。最笨的方法是检查1, 2, 3, ..., 12345。数位DP换了一种聪明得多的视角它把这些数字看作一串串“数位”。以十进制为例12345可以看作万位是1千位是2百位是3十位是4个位是5。数位DP的核心思想是从最高位开始一位一位地“构造”数字并在构造过程中动态记录和维护那些影响最终计数结果的“状态”。对于我们的二进制问题状态就是当前已经构造的二进制位中1的个数。因为最终我们要判断这个个数是否是质数。我们不需要知道前面具体构造了101还是110只需要知道前面已经有了2个1这个信息就足够了。这就是“状态压缩”将复杂的、具体的历史路径压缩成一个简单的、足以决定未来的关键参数。那么如何“构造”呢这里就引出了数位DP的两种经典实现范式记忆化搜索DFS Memoization模拟深度优先搜索的过程从最高位递归到下一位。在每一位根据是否受到“上限”约束决定当前位可以填0还是1。同时将“当前处理到第几位”、“当前1的个数”、“是否处于上限约束中”这三个关键信息组合成一个状态进行缓存记忆化。如果后续搜索遇到相同的状态就直接返回缓存的结果避免重复计算。递推Iterative DP采用更符合动态规划“表格填充”直觉的方式。我们定义dp[i][j]表示处理完前i位从高位开始且当前1的个数为j的无上限约束的方案数。然后通过状态转移方程从i位推导i1位的方案数。最后再利用这个“无上限”的DP表通过“数位拆分”和容斥思想[L,R]区间内的数量 f(R) - f(L-1)计算出有限定范围的答案。两种方法殊途同归。记忆化搜索更直观代码更像是在“模拟搜索过程”思维负担相对较小递推法则更底层需要更清晰地定义状态和转移但有时在空间优化上更有优势。下面我们就用这道二进制质数题作为战场将这两种武器都演练一遍。3. 战场准备问题定义、质数判断与数位拆分在开始DP之前我们需要做好几项基础的准备工作这些准备工作清晰与否直接影响到后续DP状态设计的正确性。3.1 明确问题与输入输出题目求在区间[L, R]1 L R 10^18中二进制表示里1的个数为质数的整数有多少个。 输入两个长整型L和R。 输出一个整数表示满足条件的数字个数。3.2 高效的质数判断由于R最大为10^18其二进制最多有60位因为2^60 ≈ 1.15e18。所以一个数二进制中1的个数最多为60。我们需要判断的是cnt1的个数是否为质数而cnt的范围是[0, 60]。这个范围非常小我们完全可以在程序开始时预处理出0到60之间所有的质数。这是一个典型的“空间换时间”和“预处理”思想。# 预处理 0-60 之间的质数 def preprocess_primes(limit60): is_prime [True] * (limit 1) is_prime[0] is_prime[1] False # 0和1不是质数 for i in range(2, int(limit**0.5) 1): if is_prime[i]: for j in range(i*i, limit1, i): is_prime[j] False # 我们只关心哪些数是质数可以存一个集合或布尔数组 prime_set {i for i, v in enumerate(is_prime) if v} # 对于本题1的个数为0或1时肯定不是质数但为了逻辑清晰我们还是用集合判断 return prime_set prime_set preprocess_primes(60) # 全局变量方便调用这样在DP过程中我们只需要检查当前累计的1的个数cnt是否在prime_set中操作是O(1)的。3.3 数位拆分将数字转化为位数组数位DP处理的是“位”。我们需要把上限数字R或L-1转换成二进制位数组以便逐位处理。def get_digits(num): 将数字转换为二进制位列表高位在前。例如 5 - [1, 0, 1] if num 0: return [0] digits [] while num 0: digits.append(num 1) # 取最低位 num 1 # 右移一位 return digits[::-1] # 反转使高位在前 # 示例处理 R5 # digits_R [1, 0, 1] (二进制101)高位在前的顺序符合我们从前向后从最高位向最低位进行DP或搜索的习惯。3.4 核心思路前缀和转化直接计算区间[L, R]比较麻烦因为有两个边界。数位DP的经典技巧是将其转化为两个前缀和相减ans(L, R) f(R) - f(L-1)其中f(X)表示区间[0, X]内满足条件的数的个数。这样我们只需要实现一个函数f(num)来计算从0到num的答案问题就简化为了有上限约束的数位统计。准备工作就绪接下来进入核心环节实现f(num)函数。我们将分别用记忆化搜索和递推两种方式来实现它。4. 解法一记忆化搜索DFS Memoization记忆化搜索是理解数位DP最直观的方式。它本质上是一个深度优先搜索但加入了“记忆”来剪枝避免重复计算相同状态的子树。4.1 状态设计与记忆化数组我们需要定义在搜索到某个位置时哪些信息足以唯一确定后续的搜索结果。对于本题关键信息有三个pos: 当前正在处理第几位从最高位开始下标通常从0或1开始。它决定了搜索的深度。cnt: 从最高位到当前位之前已经填了多少个1。这是我们的核心计数状态。limit: 这是一个布尔值表示当前位是否受到“上限”的约束。这是数位DP中最精妙也最容易出错的部分。为什么需要limit状态当我们计算f(1010)二进制时我们是在构造所有不超过1010的数。如果之前填的位已经小于上限对应位比如最高位我们填了0而上限最高位是1那么从这一刻起后面的每一位都可以自由填0或1因为无论怎么填整个数都不会超过上限。此时limit False无约束。如果之前填的位都等于上限对应位比如我们前两位填了1和0正好等于上限10那么当前位能填的最大值就受限于上限的当前位。如果上限当前位是1我们可以填0或1如果是0则只能填0。此时limit True有约束。limit这个状态直接影响当前位的选择范围进而影响后续搜索树的大小所以它必须作为记忆化状态的一部分。否则缓存的结果就是错误的因为它可能是在无约束情况下计算的却被用到了有约束的场景。因此我们定义记忆化数组memo[pos][cnt][limit]。但注意limit只有两种情况True/False而pos最多60cnt最多60。在Python中我们可以用一个三维字典或者列表来存储。为了效率通常使用lru_cache装饰器来实现记忆化将函数参数自动作为缓存键。4.2 DFS函数定义与流程我们设计一个递归函数dfs(pos, cnt, limit)含义在构造第pos位时之前已经积累了cnt个1且是否处于上限约束状态limit返回从这一状态开始构造完所有低位最终能得到多少个满足条件的数即二进制1的个数为质数。参数pos: 当前处理位索引。我们从最高位len(digits)-1开始向低位0递归。当pos 0时说明所有位已处理完。cnt: 当前已构造的位中1的个数。limit: 布尔值表示当前位是否受上限数字对应位的约束。返回满足条件的方案数。递归流程递归终点如果pos -1说明已经成功构造了一个完整的数字。此时我们只需要判断这个数字的1的个数即cnt是否为质数。如果是返回1表示这是一个有效方案否则返回0。检查记忆化如果当前状态(pos, cnt, limit)已经被计算过直接返回缓存的结果。确定当前位可选范围up_limit digits[pos] if limit else 1。如果受约束limitTrue当前位最大能填digits[pos]上限的该位值如果不受约束limitFalse当前位最大能填1二进制下最大数字。当前位可以填0或1但不能超过up_limit。递归搜索并累加初始化res 0。遍历当前位可能的取值i0或1且i up_limit。计算新的cnt_next cnt (1 if i 1 else 0)。计算新的limit_next limit and (i up_limit)。这个逻辑是只有当前状态是受约束的limitTrue并且当前位填的值等于了上限值i up_limit下一位才会继续受约束否则下一位就自由了limit_nextFalse。递归调用dfs(pos-1, cnt_next, limit_next)将结果累加到res。记忆化并返回将res存入记忆化缓存对应(pos, cnt, limit)状态然后返回res。4.3 完整代码实现与解析from functools import lru_cache def solve_memoization(L, R): # 1. 预处理质数集合 prime_set preprocess_primes(60) # 2. 定义记忆化搜索函数 def f(num): if num 0: return 0 digits get_digits(num) # 获取二进制位列表高位在前 lru_cache(maxsizeNone) def dfs(pos, cnt, limit): pos: 当前处理位索引从最高位 len(digits)-1 开始向 0 递减 cnt: 当前已构造的位中1的个数 limit: 当前位是否受上限约束 # 递归终点所有位处理完毕 if pos -1: # 判断1的个数是否为质数 return 1 if cnt in prime_set else 0 up_limit digits[pos] if limit else 1 res 0 for i in range(up_limit 1): # i 可以是 0 或 1 cnt_next cnt (1 if i 1 else 0) # 关键更新下一位的limit状态 limit_next limit and (i up_limit) res dfs(pos - 1, cnt_next, limit_next) return res # 从最高位开始搜索初始cnt0初始状态一定是受约束的limitTrue return dfs(len(digits) - 1, 0, True) # 3. 利用前缀和公式计算答案 return f(R) - f(L - 1) # 测试样例 if __name__ __main__: # 假设题目样例区间 [1, 10] # 二进制及1的个数1(1), 2(1), 3(2), 4(1), 5(2), 6(2), 7(3), 8(1), 9(2), 10(2) # 质数有2, 3, 2, 2, 3, 2, 2 - 对应数字 3,5,6,7,9,10 (1的个数为2或3) # 所以答案是 6 print(solve_memoization(1, 10)) # 预期输出 64.4 记忆化搜索的优缺点与调试心得优点思维直观代码流程就是模拟构造数字的过程容易理解和调试。状态定义灵活lru_cache自动处理状态缓存无需手动管理多维数组。处理复杂条件方便如果题目条件更复杂比如需要记录前导零、数字是否已经非零、某种模数状态等只需要在dfs函数中增加相应的状态参数即可扩展性强。缺点递归深度位数较多时如60位递归深度可能引发栈溢出风险虽然在Python中60层通常没问题但需要注意。缓存状态数状态数是pos * cnt * 2在本题中最大约为60 * 60 * 2 7200很小。但对于状态更复杂的问题可能会占用较多内存。调试技巧打印递归树在递归函数开头打印pos, cnt, limit观察搜索路径。验证小数据用暴力枚举法计算小范围如1-1000的答案与记忆化搜索的结果对比这是验证算法正确性的黄金标准。重点检查limitlimit的更新逻辑limit_next limit and (i up_limit)是核心务必理解透彻。可以手动模拟一个例子比如num5 (101)跟踪limit值的变化。5. 解法二递推迭代动态规划递推法采用了更经典的DP表格填充思路。它先计算一个“无上限”情况下的通用DP表然后利用这个表和上限数字的位信息“拼凑”出最终答案。5.1 状态定义与无上限DP表我们定义dp[i][j]i: 表示已经考虑完了从最高位开始的连续 i 位或者说我们正在处理一个长度为n的二进制数dp[i][j]表示所有长度为i的二进制前缀中蕴含的信息。j: 表示在这i位中1的个数为j。dp[i][j]的值表示有多少种长度为i的二进制前缀其中1的个数为j。这里的关键是“无上限”即这些前缀对应的位每一位都可以自由选择0或1。状态转移方程 如何从dp[i][j]得到dp[i1][?]呢当我们为当前长度为i的前缀增加第i1位时有两种选择第i1位填0那么新前缀中1的个数不变还是j。所以dp[i1][j]可以从dp[i][j]转移过来。第i1位填1那么新前缀中1的个数变为j1。所以dp[i1][j1]可以从dp[i][j]转移过来。因此转移方程为dp[i1][j] dp[i][j]当前位填0dp[i1][j1] dp[i][j]当前位填1初始化dp[0][0] 1。这表示一个长度为0的前缀即还没有任何位其中1的个数为0有1种情况可以理解为空数字。这是一个经典的起点状态。5.2 利用DP表计算 f(num)数位拼凑法现在我们有了dp表它记录了所有可能前缀的计数。如何计算f(num)即不超过num的所有数中满足条件的个数呢我们再次将num转换为二进制数组digits高位在前长度为n。我们的思路是从最高位开始逐位决定“固定”某些位与num相同并在某一位“放低”以产生小于num的数然后利用dp表快速计算后续位的组合数。具体步骤如下初始化答案ans 0以及一个变量pre_cnt 0记录在“固定”的位中已经出现的1的个数。从最高位i 0遍历到最低位i n-1 a. 设当前位digits[i]的值为cur_bit。 b.如果cur_bit 1这是一个关键点。我们可以选择在这一位填0这样就保证了整个数一定小于num因为高位相同当前位更小。如果我们选择填0那么当前位之后的所有位总共有n - i - 1位都可以自由选择0或1无上限约束。对于这些自由位我们已经固定了前缀中1的个数为pre_cnt因为当前位填了0pre_cnt不变。我们需要统计在剩下的rest_len n - i - 1位中填上若干1使得最终的1总个数为质数的方案数。 - 遍历所有可能的、在剩余位中新增的1的个数kk从0到rest_len。 - 那么最终的总1数就是total_cnt pre_cnt k。 - 如果total_cnt是质数那么这种“当前位填0后面自由填”的方案数就贡献了dp[rest_len][k]种dp[rest_len][k]正好表示长度为rest_len的二进制串中有k个1的方案数。 - 所以ans sum(dp[rest_len][k] for k in range(rest_len1) if (pre_cnt k) in prime_set)。 c. 无论cur_bit是0还是1在处理完当前位的“放低”可能性后我们都需要“固定”当前位与num相同即填cur_bit以便继续处理下一位。所以更新pre_cnt cur_bit如果当前位是1则固定后1的个数增加。 d. 如果cur_bit 0则没有“放低”的可能性因为填0已经和上限相同填负数不可能直接进入步骤c。循环结束后上面的循环处理了所有“在某一位放低从而小于num”的情况。但还有一种情况没有包含数字本身等于num。我们在循环中一直固定每一位与num相同走到了最后。所以循环结束后pre_cnt就是num本身二进制中1的个数。我们需要判断它是否为质数如果是则答案ans需要加1。5.3 完整代码实现与解析def solve_iterative_dp(L, R): # 1. 预处理质数集合 prime_set preprocess_primes(60) max_len 60 # 10^18 2^60 # 2. 预处理无上限DP表 dp[i][j] # dp[i][j]: 长度为i的二进制串中恰好有j个1的方案数 dp [[0] * (max_len 1) for _ in range(max_len 1)] dp[0][0] 1 for i in range(max_len): for j in range(i 1): # 长度为i的串1的个数j不会超过i if dp[i][j] 0: # 第i1位填0 dp[i1][j] dp[i][j] # 第i1位填1 dp[i1][j1] dp[i][j] # 3. 定义计算 f(num) 的函数 def f(num): if num 0: return 0 digits get_digits(num) n len(digits) ans 0 pre_cnt 0 # 记录固定前缀中1的个数 for i in range(n): cur_bit digits[i] rest_len n - i - 1 # 当前位之后的剩余位数 # 如果当前上限位是1我们可以尝试在这一位填0从而后面位自由 if cur_bit 1: # 遍历后面自由位中可以新增的1的个数k for k in range(rest_len 1): total_cnt pre_cnt 0 k # 当前位填0所以0 if total_cnt in prime_set: ans dp[rest_len][k] # 后面rest_len位中选k个1的方案数 # 固定当前位与上限相同继续处理下一位 pre_cnt cur_bit # 循环结束后pre_cnt就是num本身1的个数检查num本身是否合法 if pre_cnt in prime_set: ans 1 return ans # 4. 计算最终答案 return f(R) - f(L - 1) # 测试应与记忆化搜索结果一致 print(solve_iterative_dp(1, 10)) # 预期输出 65.4 递推法的优缺点与思维难点优点非递归没有递归深度限制更适合位数极多的场景虽然本题60位没问题。预处理高效dp表只需计算一次之后所有f(num)的计算都复用同一张表在需要多次查询不同区间时优势明显。思维锻炼“数位拼凑”的过程锻炼了对数位DP本质的理解。缺点思维难度高“拼凑”的过程比记忆化搜索更绕容易在计算“放低”位和“固定”位的逻辑上出错。代码稍复杂需要手动维护dp表和f(num)的拼凑逻辑。思维难点解析为什么只处理cur_bit 1的情况因为只有当前上限位是1时我们填0才能保证构造的数小于上限。如果当前位是0我们填0是与上限相同继续受约束填1则会导致数大于上限不允许。dp表的意义dp[rest_len][k]代表了在rest_len个完全自由的位上放置k个1的方案数即组合数C(rest_len, k)。递推法其实就是用DP的方式预计算了组合数。与记忆化搜索的联系递推法中的“拼凑”本质上是在模拟记忆化搜索中那些limitFalse的分支。当我们在某一位“放低”填0就相当于进入了limitFalse的状态后续所有位都可以自由选择其方案数可以直接通过预计算的组合数dp表得到无需递归。6. 实战对比与边界条件处理为了确保我们的解法是健壮的我们需要进行全面的测试和边界条件分析。6.1 暴力枚举验证对于小范围数据写一个暴力程序进行验证是最可靠的方法。def brute_force(L, R): def count_ones(x): cnt 0 while x: cnt x 1 x 1 return cnt prime_set preprocess_primes(60) ans 0 for num in range(L, R 1): if count_ones(num) in prime_set: ans 1 return ans # 测试多组随机小数据 import random random.seed(42) for _ in range(10): L random.randint(1, 1000) R random.randint(L, L 500) ans_memo solve_memoization(L, R) ans_iter solve_iterative_dp(L, R) ans_brute brute_force(L, R) print(fL{L}, R{R}: Memo{ans_memo}, Iter{ans_iter}, Brute{ans_brute}, Check{ans_memoans_iterans_brute})如果所有输出都是True那么恭喜你两种DP算法的正确性得到了初步验证。6.2 边界条件与易错点L1, R11的二进制是1有1个11不是质数答案应为0。L1, R21(1个1非质数)2(二进制101个1非质数)答案应为0。L1, R31(非)2(非)3(二进制112个1是质数)答案应为1。L0的情况题目给定L 1但我们的f(L-1)当L1时会计算f(0)。0的二进制表示通常被认为是0有0个10不是质数。我们的get_digits函数和DP逻辑需要正确处理num0。上面的实现中get_digits(0)返回[0]在记忆化搜索中dfs会处理pos从0开始最终判断cnt0不在质数集中在递推法中f(0)的循环n1,digits[0]cur_bit0不会进入if cur_bit1分支最后pre_cnt0不在质数集中返回0。符合预期。大数测试可以用Python的大整数能力测试一个较大的范围比如[1, 10**12]确保程序不会超时或内存溢出。两种DP解法对于10^18都是瞬间出结果。6.3 性能分析与选择建议时间复杂度记忆化搜索状态数约为O(位数 * 最大1的个数 * 2) O(60*60*2)O(7200)每个状态的计算是常数时间。计算一个f(num)的复杂度约为O(状态数)。计算f(R)和f(L-1)两次总复杂度可以忽略不计。递推法预处理dp表O(60^2)。计算一个f(num)需要遍历其每一位最多60位对于每一位为1的情况需要内层循环rest_len1次最多60次。最坏情况下f(num)复杂度约为O(60^2)。同样非常快。空间复杂度记忆化搜索缓存状态所占空间同样是O(位数 * 最大1的个数 * 2)。递推法dp表O(60^2)。如何选择新手入门、调试复杂条件强烈推荐记忆化搜索。它更符合直觉状态设计灵活通过增加参数就能处理前导零、模数、相邻位关系等复杂约束。追求极致性能、需要多次查询如果题目需要查询很多不同的[L, R]区间递推法更有优势因为dp表只需构建一次后续每次f(num)计算都很快。应对笔试面试掌握记忆化搜索模板足以解决绝大多数数位DP问题且代码简洁不易出错。7. 举一反三数位DP的通用模板与变种这道二进制质数题是一个经典的数位DP入门题。掌握了它你就掌握了数位DP的骨架。下面我总结一个记忆化搜索的通用模板并说明如何适配其他问题。7.1 记忆化搜索通用模板框架from functools import lru_cache def digit_dp_template(num): digits get_digits(num) # 按题目要求转换为数位列表二进制、十进制等 lru_cache(maxsizeNone) def dfs(pos, state, limit, lead): pos: 当前处理位索引从高位向低位 state: 一个表示“状态”的参数可以是计数、模数、某种标志等。本题是 cnt1的个数。 limit: 是否受到上限约束 lead: 是否有前导零对于处理数字实际值、不允许前导零的题目很重要 # 1. 递归终点 if pos -1: return check(state) # 根据最终状态判断是否是一个合法数字 # 2. 如果不受约束且无前导零问题可以尝试记忆化返回注意有lead时通常不记忆化或lead作为状态一部分 if not limit and not lead and (pos, state) in memo: return memo[(pos, state)] up_limit digits[pos] if limit else 9 # 十进制上限是9二进制是1 res 0 for i in range(up_limit 1): # 处理前导零如果lead为真且当前位为0则数字仍然处于前导零状态 next_lead lead and (i 0) # 根据当前位i更新状态state - next_state next_state update_state(state, i, next_lead) # 更新limit状态 next_limit limit and (i up_limit) res dfs(pos-1, next_state, next_limit, next_lead) # 3. 记忆化存储仅在无约束、无前导零时缓存 if not limit and not lead: memo[(pos, state)] res return res # 初始状态从最高位开始状态初始值处于上限约束可能有前导零 return dfs(len(digits)-1, init_state, True, True)关键点适配get_digits: 根据题目进制转换。state: 定义需要携带的状态。本题是cnt如果是“数字和模X为Y”则state可以是(sum_mod)如果是“不能出现连续两个1”则state可以是last_bit上一位是0还是1。check(state): 递归终点时根据最终状态判断该数字是否计入答案。update_state(state, i, lead): 根据当前位i和是否前导零更新状态。lead: 对于统计数字本身的性质如数字和、数位乘积前导零不影响。但对于统计“数位”本身的模式如“不含前导零的二进制数”lead就很重要。7.2 经典变种题目思路点拨题目求[L, R]间十进制表示下数位之和能整除K的数的个数。状态设计state为当前数位之和模K的值sum_mod。终点判断pos -1时检查sum_mod 0。状态更新next_state (sum_mod i) % K。注意K可能很大但数位之和有上限如十进制下每位数最大9位数最多几十所以sum_mod范围是[0, K-1]如果K大于最大可能和可以特殊处理。题目求[L, R]间二进制表示下不包含连续两个1的数的个数即不存在“11”子串。状态设计state为上一个位last_bit是0还是1。初始时可以设为0表示前面没有位或者上一位是0。终点判断pos -1时返回1只要成功构造到底就是一个合法数字。状态更新与剪枝如果last_bit 1且当前想填i 1则非法跳过。否则next_state i。前导零此题中前导零不影响“连续1”的判断lead参数可以省略或始终为False。题目求[L, R]间既是回文数又是质数的数的个数范围较小如1e7以内可先筛质数。这题结合了数位DP和数学。可以先筛出范围内的质数再用数位DP统计回文数最后取交集。或者用数位DP构造回文数因为回文数可以由前半部分决定再判断是否是质数。状态设计需要能表示回文数的构造过程。7.3 从理解到精通我的训练建议第一步吃透模板。把二进制质数这道题的两种解法反复敲几遍直到能默写并完全理解limit和状态转移的每一个细节。第二步专项练习。在各大OJ如洛谷、LeetCode上搜索“数位DP”标签的题目从简单开始。每做一题思考状态如何设计并尝试用模板解决。第三步总结归纳。准备一个笔记本记录不同类型题目对应的state设计计数类如1的个数state cnt模运算类如数位和模Kstate sum_mod位运算/模式类如不含连续1state last_bit复杂条件类如同时满足多个state可能是一个元组(cnt, sum_mod, last_bit, ...)但要注意状态不能太多否则复杂度爆炸。第四步挑战综合题。尝试一些结合了数位DP和其他知识如组合数学、状压DP的题目。数位DP的难点不在于DP本身而在于如何将“数字区间满足某性质”这一条件转化为在“数位”这一维度上可计算、可记忆的“状态”。一旦掌握了这种转化思想你会发现它是一把打开数字计数问题的万能钥匙。无论是蓝桥杯、ACM还是面试笔试这类问题都将从拦路虎变成你的得分点。