1. 从“数数”到“计数”蓝桥杯计数问题的本质如果你正准备参加蓝桥杯看到“计数”这个分类是不是觉得就是简单的数数比如数一数一个数组里有多少个偶数或者统计一个字符串里某个字母出现的次数如果这么想那你可能低估了蓝桥杯“计数”类题目的深度。我参加过几届蓝桥杯也带过不少学生发现很多同学在“计数”题上栽跟头不是因为题目有多难而是因为思维还停留在“枚举”的层面一旦数据规模稍大程序就超时或者根本无从下手。实际上蓝桥杯中的“计数”问题核心是组合数学和动态规划思想的应用。它考察的不是你能不能写一个循环去数而是你能不能找到一种高效、不重不漏的计算方法。比如给你一个复杂的图形问有多少条不同的路径或者给你一组有约束条件的数字问能组成多少个合法的序列。这些问题如果你试图用程序去模拟所有可能的情况即“暴力枚举”在竞赛的时间和数据限制下几乎必然失败。备战这类题目关键在于思维模式的转变从“如何数出来”转变为“如何算出来”。你需要掌握一些核心的“计数原理”和“计数模型”并熟练运用动态规划这个强大的工具来组织这些计算。这就像给你一堆积木基本计数原理你需要用图纸动态规划状态设计把它们搭建成一座大厦解决复杂问题而不是一块一块地去数有多少种搭法。接下来的内容我将结合蓝桥杯真题和常见模型拆解“计数”问题的核心解法分享从基础原理到实战应用的完整路径以及我在备赛和教学中总结出的那些容易踩坑的细节。2. 计数问题的两大基石加法与乘法原理所有复杂的计数问题都建立在最基础的两个原理之上加法原理和乘法原理。理解它们不仅是解题的第一步更是设计正确状态转移方程的关键。2.1 加法原理分类的智慧加法原理很简单完成一件事有n类互斥的方法第一类有a1种方法第二类有a2种方法……第n类有an种方法那么完成这件事总共有a1 a2 ... an种方法。关键在于“互斥”。比如从北京到上海可以坐飞机3个航班或者坐高铁4个车次。坐飞机和坐高铁是两类不同的、互不重叠的方法所以总共有3 4 7种出行方案。蓝桥杯实战场景题目常常不会直接问这么简单的问题。它会将“类”隐藏起来。例如求1到n中与m互质的数有多少个一种思路是总数n减去与m不互质的数。而与m不互质的数可以根据m的质因数利用容斥原理来求容斥原理本质上是加法原理的推广。这里“与质因数p1整除”、“与质因数p2整除”……这些集合之间可能有重叠就不是简单的加法了需要用到容斥。但思考的起点仍然是“分类”。注意当各类方法之间不互斥即存在重叠时直接相加会导致重复计数。这时就需要用到容斥原理来去重。容斥原理是加法原理在处理有重叠集合时的扩展公式为|A∪B| |A| |B| - |A∩B|对于更多集合也有类似公式。在蓝桥杯计数题中识别出“重叠”并正确应用容斥是一个高频考点。2.2 乘法原理分步的艺术乘法原理完成一件事需要n个步骤第一步有a1种方法第二步有a2种方法……第n步有an种方法且每一步的选择相互独立即选择不受前一步影响那么完成这件事总共有a1 × a2 × ... × an种方法。比如从北京经南京到上海。第一步北京到南京有2种交通方式飞机、高铁第二步从南京到上海有3种交通方式汽车、动车、城际铁路。因为两步是连续的且选择独立所以总共有2 × 3 6种完整的出行方案。蓝桥杯实战场景乘法原理的应用更为广泛尤其是在排列组合和动态规划中。例如用1、2、3、4、5组成没有重复数字的三位数有多少个我们可以分三步选百位5种选择、选十位剩下4种选择、选个位剩下3种选择。所以总数是5 × 4 × 3 60。这就是一个简单的排列数P(5,3)。更复杂的比如“网格路径问题”在一个m×n的网格中从左上角走到右下角每次只能向右或向下有多少种走法我们可以理解为总共需要走(m-1)(n-1)步其中必须向右走(n-1)步向下走(m-1)步。问题转化为在这总步数中选择(n-1)个位置来放置“向右”这个动作剩下的位置自然放“向下”。所以答案是组合数C((m-1)(n-1), n-1)。这个转化过程就隐含了乘法原理的思想——确定每一步的方向选择。我的踩坑心得最容易出错的地方是混淆“分类”和“分步”。一个简单的判断方法是如果做完一步事情还没完成需要继续做下一步那就是“分步”用乘法如果几种方法都能独立完成整件事那就是“分类”用加法。在动态规划中状态转移往往对应着“分步”操作所以状态转移方程里常常是求和对应多种来源状态分类或取最值而计算某个状态的方法数时则是对能转移到它的所有前驱状态的方法数进行求和加法原理而这个转移过程本身又体现了从前驱状态到当前状态这一步的“选择”乘法原理已蕴含在状态定义中。3. 动态规划计数问题的万能框架当问题规模变大且有明显的阶段性或状态性时动态规划DP就成了计数问题的“标准解法”。DP的核心思想是把大问题分解为小问题并记住这些小问题的解避免重复计算从而高效地得到大问题的解。对于计数问题DP状态dp[i]通常表示“达到状态i有多少种方法”。3.1 线性DP爬楼梯与硬币兑换这是最经典的DP计数模型。模型1爬楼梯。一次可以爬1级或2级台阶爬到第n级有多少种方法状态定义dp[i]表示爬到第i级台阶的方法数。状态转移要爬到第i级最后一步要么从第i-1级跨1步上来要么从第i-2级跨2步上来。这两种方式是“分类”关系且互斥。所以dp[i] dp[i-1] dp[i-2]。初始化dp[0] 1起点一种方法dp[1] 1。这其实就是斐波那契数列。模型2硬币兑换求组合数。有面值为coins [1, 2, 5]的硬币无限个要凑出总金额amount有多少种组合方式LeetCode 518. 零钱兑换 II关键点这里是求“组合数”即(1,2)和(2,1)算同一种。为了不重复计数我们必须固定硬币的考虑顺序。状态定义dp[i][j]表示只使用前i种硬币coins[0...i-1]凑出金额j的组合数。通常可以优化为一维dp[j]。一维DP转移方程dp[j] dp[j - coin]。但必须外层循环遍历硬币内层循环遍历金额。dp [0] * (amount 1) dp[0] 1 # 凑出0元有一种方法什么都不选 for coin in coins: for j in range(coin, amount 1): dp[j] dp[j - coin]为什么这个顺序能避免重复外层循环固定了硬币的种类顺序。假设先考虑硬币1再考虑硬币2。那么在任何一种组合中硬币1总是出现在硬币2之前如果存在的话。这样就保证了(1,2)和(2,1)不会被算成两种。如果内外层循环颠倒就会变成排列数。蓝桥杯真题链接很多整数分解、方案计数问题都可以归为此类。例如将数字n拆分成若干个正整数之和求拆分数不考虑顺序。这可以通过DP解决dp[i][j]表示用1...i的数凑出j的方案数其转移与硬币问题类似。3.2 区间DP回文子串计数区间DP常用于解决子串、子序列的计数问题状态通常定义为dp[i][j]表示区间[i, j]的某种属性。经典问题给定一个字符串s统计其中回文子串的个数。暴力法枚举所有子串O(n^2)再判断是否回文O(n)总复杂度O(n^3)不可取。中心扩散法枚举每个或每两个字符作为中心向两边扩展计数。时间复杂度O(n^2)空间O(1)。这是更优解。区间DP法理解DP思想状态定义dp[i][j]表示子串s[i...j]是否是回文串布尔值。状态转移如果i j单字符肯定是回文dp[i][j] True。如果j i1两个字符dp[i][j] (s[i] s[j])。如果j i1dp[i][j] (s[i] s[j]) and dp[i1][j-1]。计算顺序由于dp[i][j]依赖于dp[i1][j-1]左下角所以需要从下到上、从左到右遍历。计数遍历所有dp[i][j]为True的计数加一。虽然对于此题DP并非最优但它揭示了区间DP的典型模式对于更复杂的子序列计数问题如有多少个不同的回文子序列非常有用。3.3 状态压缩DP棋盘放置问题当问题的状态可以用一个有限的、较小的集合表示并且每个元素只有两种状态如放/不放有/无时可以考虑状态压缩DP。通常用二进制整数来表示一个状态。经典模型在N×M的棋盘上放置棋子要求棋子不能相互攻击比如车不能在同一行/列。状态定义dp[i][state]表示处理到第i行当前行的棋子放置状态为state时前i行的总方案数。state是一个二进制数第j位为1表示第j列放了棋子。状态转移dp[i][cur_state] dp[i-1][pre_state]。转移需要满足两个条件cur_state本身是合法的例如二进制表示中不能有相邻的1如果要求棋子不能左右相邻。cur_state和pre_state之间没有冲突例如同一列不能同时有1如果要求棋子不能上下相邻。初始化dp[0][0] 1表示第0行通常作为虚拟行什么都不放有1种方案。结果sum(dp[N][all_states])即最后一行所有可能状态对应的方案数之和。蓝桥杯实战技巧预处理合法状态在DP循环开始前先枚举所有对于单行来说合法的状态例如没有两个1相邻存到一个列表valid_states中。这能大幅减少内层循环次数。预处理状态转移关系对于每一对(pre_state, cur_state)提前判断它们是否可以相邻放置即不违反列冲突规则将可转移的关系存下来。这样在DP双层循环时直接遍历这些关系即可避免每次进行位运算判断。滚动数组优化由于dp[i]只依赖于dp[i-1]可以用两个数组交替使用将空间复杂度从O(N * 2^M)降到O(2^M)。这类题目在蓝桥杯国赛和省赛中较常见需要熟练掌握二进制位的操作如判断某位是否为1(state k) 1判断状态是否有交集state1 state2 0。4. 组合数学直接计算的公式与模型有些计数问题有直接的数学公式掌握这些模型能让你在竞赛中快速解题避免复杂的DP推导。4.1 排列、组合、阶乘这是基础中的基础必须熟练。排列数 A(n, m) n! / (n-m)!从n个不同元素中取出m个元素按顺序排列。组合数 C(n, m) n! / (m! * (n-m)!)从n个不同元素中取出m个元素构成一组不计顺序。重要性质C(n, m) C(n, n-m)C(n, m) C(n-1, m-1) C(n-1, m)杨辉三角/帕斯卡公式也是组合数DP求法的依据多重集的排列/组合元素有重复公式不同需注意。蓝桥杯常见考点直接套公式的题越来越少更多的是需要你识别出问题本质是某个组合模型。例如“隔板法”用于解决“将n个相同物品分给m个不同对象每个对象至少分得1个”的问题方案数为C(n-1, m-1)。4.2 卡特兰数括号匹配与出栈序列卡特兰数是一个在组合计数中频繁出现的数列。其递推公式为C(0)1, C(n1) Σ_{i0}^{n} C(i)*C(n-i)前几项为1, 1, 2, 5, 14, 42, 132...经典模型n对括号的合法匹配序列数C(n)。n个节点的不同二叉搜索树BST数量C(n)。一个栈的进栈序列为1,2,...,n不同的出栈序列数C(n)。在网格中从(0,0)走到(n,n)只能向右或向上且不穿过对角线即yx的路径数C(n)。实战应用当你看到题目描述符合上述任何一个模型时可以直接套用卡特兰数。计算时由于n可能很大通常需要结合组合数公式和取模运算来求。公式为C(n) C(2n, n) / (n1)。4.3 容斥原理解决“至少一个”或“交集”问题当问题要求“满足至少一个条件”或者多个条件之间有重叠时容斥原理是利器。公式对于n个集合A1, A2, ..., An则至少属于其中一个集合的元素个数为|A1∪A2∪...∪An| Σ|Ai| - Σ|Ai∩Aj| Σ|Ai∩Aj∩Ak| - ... (-1)^(n1)|A1∩A2∩...∩An|蓝桥杯例题求1到1000中能被2, 3, 5中至少一个整除的数的个数。设A为被2整除的集合B为被3整除C为被5整除。|A| 1000/2 500,|B| 333,|C| 200。|A∩B| 1000/lcm(2,3)1000/6166,|A∩C|1000/10100,|B∩C|1000/1566。|A∩B∩C| 1000/lcm(2,3,5)1000/3033。根据容斥原理|A∪B∪C| 500333200 - 166-100-66 33 734。我的踩坑心得容斥原理的难点在于“符号”和“求交集大小”。对于“至少满足一个条件”的问题用上述公式。对于“一个条件都不满足”的问题可以用总数减去“至少满足一个”的数量。求多个集合的交集大小时通常是求这些条件的最小公倍数LCM相关的整除个数。在编程实现时n个条件的容斥可以通过二进制枚举所有非空子集来实现非常方便。5. 实战拆解蓝桥杯真题“高僧斗法”的计数思维让我们分析一下你提供的热词中的一道真题蓝桥杯2013年第四届真题-高僧斗法。虽然这是一道博弈论尼姆游戏的题目但其解题过程中蕴含了深刻的“状态计数”和“转化”思想对于理解计数问题的灵活性很有帮助。题目简述回忆版在一条路上有n个石子堆代表高僧的位置两个玩家轮流操作。每次操作可以选择一个石子堆拿走至少一个石子。当所有石子堆的石子数都变成0时游戏结束。最后无法操作的人输。但本题有一个关键约束每次操作不能使石子数变为负数且操作后石子堆的石子数必须呈“严格递增”序列模拟高僧的法力高低。问先手是否有必胜策略。这不是一道直接的计数题但它如何与计数关联状态表示游戏的一个状态可以用一个有序元组(a1, a2, ..., an)来表示其中a1 a2 ... an。所有可能的状态构成了一个庞大的状态空间。胜负态计数思维层面博弈论DP的核心就是给每个状态标记“必胜态(N-position)”或“必败态(P-position)”。从终点状态全是0但不符合递增可视为游戏已结束的特殊状态倒推。一个状态是必败态当且仅当它的所有可能下一步操作到达的状态都是必胜态一个状态是必胜态当且仅当它存在至少一种操作可以走到一个必败态。从计数到优化如果直接对状态空间进行DP计数计算每个状态是N还是P状态数量是组合数级别的无法计算。这就需要利用博弈论的“SG函数”和“尼姆和”理论来优化。SG函数本身可以看作是对一个状态所代表的“游戏分支”的一种数学化“计数”和“归类”。将复杂的游戏转化为尼姆堆就是找到了一个等价计数模型。对备战计数问题的启示转化思想很多复杂的计数问题可以通过建模转化为已知的经典模型如组合数、DP、卡特兰数。这道题将“约束下的取石子游戏”转化为了“尼姆游戏”。状态压缩即使不能显式地枚举所有状态我们也可以通过分析状态的特征如奇偶性、模数、异或和来对状态进行“分类计数”从而得到通用解。在这道题中通过计算“阶梯尼姆”的异或和就能直接判断必胜必败而不需要知道具体有多少个必胜态。边界与约束题目中“严格递增”的约束是关键。在你自己设计DP状态时也常常需要加入类似的约束条件例如序列中相邻元素的差值、大小关系等来定义状态这会使状态转移方程更复杂但也是解题的突破口。6. 备赛训练策略与资源推荐理解了原理和模型还需要通过大量练习来内化。以下是我总结的备赛策略6.1 分阶段刷题计划第一阶段夯实基础1-2个月目标掌握加法/乘法原理、排列组合公式、简单DP爬楼梯、硬币、最长上升子序列。资源蓝桥杯官方练习系统的“基础练习”部分。LeetCode或洛谷的简单DP题、数学题。方法每个类型找5-10道题确保能独立、快速写出正确代码。重点理解状态定义和转移方程的推导过程而不是背代码。第二阶段模型突破2-3个月目标攻克区间DP、状态压缩DP、容斥原理、卡特兰数等核心模型。资源区间DP练习回文子序列、石子合并等问题。状态压缩DP练习棋盘放置如“蒙德里安的梦想”、“小国王”、旅行商问题(TSP)的计数变种。容斥原理练习求1-n中与m个数互质的数的个数、错排问题等。卡特兰数识别模型并练习大数取模下的计算。方法针对每个模型进行专项训练。总结该模型的状态定义套路、转移方程套路和初始化技巧。整理成自己的笔记。第三阶段真题模拟与综合训练1-2个月目标在时间压力下准确识别题目所属模型并快速实现。资源蓝桥杯历年真题省赛、国赛尤其是“计数”标签下的题目。方法卡时间4小时做整套真题。赛后重点复盘哪道题没想到模型哪道题实现出错了时间分配是否合理6.2 调试与优化技巧计数问题代码常见的BUG和优化点整数溢出这是最大的坑组合数、DP结果往往增长极快。蓝桥杯通常要求对结果取模如1e97。必须时刻警惕在可能发生乘法的任何地方先取模再运算。(a * b) % mod比a * b安全。使用long long类型C或Python的大整数。初始化错误DP数组的初始值至关重要。dp[0]或dp[0][0]往往代表“空方案”或“起点”通常是1。务必结合题意仔细思考。循环顺序错误特别是在二维/多维DP以及需要优化空间时如硬币组合问题。错误的循环顺序会导致状态被错误地重复计算或遗漏。记住一个原则在计算dp[i][j]时它所依赖的子状态必须已经被计算出来。模运算下的除法组合数公式中有除法如C(n, m) n! / (m! * (n-m)!)。在取模运算中不能直接做除法需要用到乘法逆元。通常使用费马小定理求逆元当模数为质数时a / b % mod a * pow(b, mod-2, mod) % mod。在比赛中可以预处理出阶乘数组fact[]和阶乘逆元数组inv_fact[]然后C(n,m) fact[n] * inv_fact[m] % mod * inv_fact[n-m] % mod。6.3 心理建设与考场策略先暴力再优化如果一时想不到完美的DP或公式先写一个暴力搜索DFS版本。这有两个好处一是可以验证小数据样例二是暴力搜索的递归树往往能给你提供状态设计的灵感。画图辅助对于DP问题在草稿纸上画出状态转移图哪怕只是简单的箭头能极大帮助你理清思路避免混乱。测试极端情况写完代码后务必测试n0,1等边界情况。对于计数问题这些地方最容易出错。时间管理如果一道计数题卡了超过30分钟还没有清晰思路先标记去做其他题。有时做完其他题再回头可能会有新灵感。备战蓝桥杯的“计数”专题本质上是在锻炼你的数学建模能力和逻辑组织能力。它要求你将一个模糊的实际问题抽象成清晰的数学关系然后用程序高效地计算出来。这个过程充满挑战但也极具乐趣。当你看到一道复杂的题目最终被简洁的状态转移方程或优雅的数学公式解决时那种成就感是无与伦比的。多思考、多总结、多动手你会发现“计数”不再是难题而是你竞赛武器库中一件得心应手的利器。 蓝桥杯计数问题：从组合数学到动态规划的解题思维
1. 从“数数”到“计数”蓝桥杯计数问题的本质如果你正准备参加蓝桥杯看到“计数”这个分类是不是觉得就是简单的数数比如数一数一个数组里有多少个偶数或者统计一个字符串里某个字母出现的次数如果这么想那你可能低估了蓝桥杯“计数”类题目的深度。我参加过几届蓝桥杯也带过不少学生发现很多同学在“计数”题上栽跟头不是因为题目有多难而是因为思维还停留在“枚举”的层面一旦数据规模稍大程序就超时或者根本无从下手。实际上蓝桥杯中的“计数”问题核心是组合数学和动态规划思想的应用。它考察的不是你能不能写一个循环去数而是你能不能找到一种高效、不重不漏的计算方法。比如给你一个复杂的图形问有多少条不同的路径或者给你一组有约束条件的数字问能组成多少个合法的序列。这些问题如果你试图用程序去模拟所有可能的情况即“暴力枚举”在竞赛的时间和数据限制下几乎必然失败。备战这类题目关键在于思维模式的转变从“如何数出来”转变为“如何算出来”。你需要掌握一些核心的“计数原理”和“计数模型”并熟练运用动态规划这个强大的工具来组织这些计算。这就像给你一堆积木基本计数原理你需要用图纸动态规划状态设计把它们搭建成一座大厦解决复杂问题而不是一块一块地去数有多少种搭法。接下来的内容我将结合蓝桥杯真题和常见模型拆解“计数”问题的核心解法分享从基础原理到实战应用的完整路径以及我在备赛和教学中总结出的那些容易踩坑的细节。2. 计数问题的两大基石加法与乘法原理所有复杂的计数问题都建立在最基础的两个原理之上加法原理和乘法原理。理解它们不仅是解题的第一步更是设计正确状态转移方程的关键。2.1 加法原理分类的智慧加法原理很简单完成一件事有n类互斥的方法第一类有a1种方法第二类有a2种方法……第n类有an种方法那么完成这件事总共有a1 a2 ... an种方法。关键在于“互斥”。比如从北京到上海可以坐飞机3个航班或者坐高铁4个车次。坐飞机和坐高铁是两类不同的、互不重叠的方法所以总共有3 4 7种出行方案。蓝桥杯实战场景题目常常不会直接问这么简单的问题。它会将“类”隐藏起来。例如求1到n中与m互质的数有多少个一种思路是总数n减去与m不互质的数。而与m不互质的数可以根据m的质因数利用容斥原理来求容斥原理本质上是加法原理的推广。这里“与质因数p1整除”、“与质因数p2整除”……这些集合之间可能有重叠就不是简单的加法了需要用到容斥。但思考的起点仍然是“分类”。注意当各类方法之间不互斥即存在重叠时直接相加会导致重复计数。这时就需要用到容斥原理来去重。容斥原理是加法原理在处理有重叠集合时的扩展公式为|A∪B| |A| |B| - |A∩B|对于更多集合也有类似公式。在蓝桥杯计数题中识别出“重叠”并正确应用容斥是一个高频考点。2.2 乘法原理分步的艺术乘法原理完成一件事需要n个步骤第一步有a1种方法第二步有a2种方法……第n步有an种方法且每一步的选择相互独立即选择不受前一步影响那么完成这件事总共有a1 × a2 × ... × an种方法。比如从北京经南京到上海。第一步北京到南京有2种交通方式飞机、高铁第二步从南京到上海有3种交通方式汽车、动车、城际铁路。因为两步是连续的且选择独立所以总共有2 × 3 6种完整的出行方案。蓝桥杯实战场景乘法原理的应用更为广泛尤其是在排列组合和动态规划中。例如用1、2、3、4、5组成没有重复数字的三位数有多少个我们可以分三步选百位5种选择、选十位剩下4种选择、选个位剩下3种选择。所以总数是5 × 4 × 3 60。这就是一个简单的排列数P(5,3)。更复杂的比如“网格路径问题”在一个m×n的网格中从左上角走到右下角每次只能向右或向下有多少种走法我们可以理解为总共需要走(m-1)(n-1)步其中必须向右走(n-1)步向下走(m-1)步。问题转化为在这总步数中选择(n-1)个位置来放置“向右”这个动作剩下的位置自然放“向下”。所以答案是组合数C((m-1)(n-1), n-1)。这个转化过程就隐含了乘法原理的思想——确定每一步的方向选择。我的踩坑心得最容易出错的地方是混淆“分类”和“分步”。一个简单的判断方法是如果做完一步事情还没完成需要继续做下一步那就是“分步”用乘法如果几种方法都能独立完成整件事那就是“分类”用加法。在动态规划中状态转移往往对应着“分步”操作所以状态转移方程里常常是求和对应多种来源状态分类或取最值而计算某个状态的方法数时则是对能转移到它的所有前驱状态的方法数进行求和加法原理而这个转移过程本身又体现了从前驱状态到当前状态这一步的“选择”乘法原理已蕴含在状态定义中。3. 动态规划计数问题的万能框架当问题规模变大且有明显的阶段性或状态性时动态规划DP就成了计数问题的“标准解法”。DP的核心思想是把大问题分解为小问题并记住这些小问题的解避免重复计算从而高效地得到大问题的解。对于计数问题DP状态dp[i]通常表示“达到状态i有多少种方法”。3.1 线性DP爬楼梯与硬币兑换这是最经典的DP计数模型。模型1爬楼梯。一次可以爬1级或2级台阶爬到第n级有多少种方法状态定义dp[i]表示爬到第i级台阶的方法数。状态转移要爬到第i级最后一步要么从第i-1级跨1步上来要么从第i-2级跨2步上来。这两种方式是“分类”关系且互斥。所以dp[i] dp[i-1] dp[i-2]。初始化dp[0] 1起点一种方法dp[1] 1。这其实就是斐波那契数列。模型2硬币兑换求组合数。有面值为coins [1, 2, 5]的硬币无限个要凑出总金额amount有多少种组合方式LeetCode 518. 零钱兑换 II关键点这里是求“组合数”即(1,2)和(2,1)算同一种。为了不重复计数我们必须固定硬币的考虑顺序。状态定义dp[i][j]表示只使用前i种硬币coins[0...i-1]凑出金额j的组合数。通常可以优化为一维dp[j]。一维DP转移方程dp[j] dp[j - coin]。但必须外层循环遍历硬币内层循环遍历金额。dp [0] * (amount 1) dp[0] 1 # 凑出0元有一种方法什么都不选 for coin in coins: for j in range(coin, amount 1): dp[j] dp[j - coin]为什么这个顺序能避免重复外层循环固定了硬币的种类顺序。假设先考虑硬币1再考虑硬币2。那么在任何一种组合中硬币1总是出现在硬币2之前如果存在的话。这样就保证了(1,2)和(2,1)不会被算成两种。如果内外层循环颠倒就会变成排列数。蓝桥杯真题链接很多整数分解、方案计数问题都可以归为此类。例如将数字n拆分成若干个正整数之和求拆分数不考虑顺序。这可以通过DP解决dp[i][j]表示用1...i的数凑出j的方案数其转移与硬币问题类似。3.2 区间DP回文子串计数区间DP常用于解决子串、子序列的计数问题状态通常定义为dp[i][j]表示区间[i, j]的某种属性。经典问题给定一个字符串s统计其中回文子串的个数。暴力法枚举所有子串O(n^2)再判断是否回文O(n)总复杂度O(n^3)不可取。中心扩散法枚举每个或每两个字符作为中心向两边扩展计数。时间复杂度O(n^2)空间O(1)。这是更优解。区间DP法理解DP思想状态定义dp[i][j]表示子串s[i...j]是否是回文串布尔值。状态转移如果i j单字符肯定是回文dp[i][j] True。如果j i1两个字符dp[i][j] (s[i] s[j])。如果j i1dp[i][j] (s[i] s[j]) and dp[i1][j-1]。计算顺序由于dp[i][j]依赖于dp[i1][j-1]左下角所以需要从下到上、从左到右遍历。计数遍历所有dp[i][j]为True的计数加一。虽然对于此题DP并非最优但它揭示了区间DP的典型模式对于更复杂的子序列计数问题如有多少个不同的回文子序列非常有用。3.3 状态压缩DP棋盘放置问题当问题的状态可以用一个有限的、较小的集合表示并且每个元素只有两种状态如放/不放有/无时可以考虑状态压缩DP。通常用二进制整数来表示一个状态。经典模型在N×M的棋盘上放置棋子要求棋子不能相互攻击比如车不能在同一行/列。状态定义dp[i][state]表示处理到第i行当前行的棋子放置状态为state时前i行的总方案数。state是一个二进制数第j位为1表示第j列放了棋子。状态转移dp[i][cur_state] dp[i-1][pre_state]。转移需要满足两个条件cur_state本身是合法的例如二进制表示中不能有相邻的1如果要求棋子不能左右相邻。cur_state和pre_state之间没有冲突例如同一列不能同时有1如果要求棋子不能上下相邻。初始化dp[0][0] 1表示第0行通常作为虚拟行什么都不放有1种方案。结果sum(dp[N][all_states])即最后一行所有可能状态对应的方案数之和。蓝桥杯实战技巧预处理合法状态在DP循环开始前先枚举所有对于单行来说合法的状态例如没有两个1相邻存到一个列表valid_states中。这能大幅减少内层循环次数。预处理状态转移关系对于每一对(pre_state, cur_state)提前判断它们是否可以相邻放置即不违反列冲突规则将可转移的关系存下来。这样在DP双层循环时直接遍历这些关系即可避免每次进行位运算判断。滚动数组优化由于dp[i]只依赖于dp[i-1]可以用两个数组交替使用将空间复杂度从O(N * 2^M)降到O(2^M)。这类题目在蓝桥杯国赛和省赛中较常见需要熟练掌握二进制位的操作如判断某位是否为1(state k) 1判断状态是否有交集state1 state2 0。4. 组合数学直接计算的公式与模型有些计数问题有直接的数学公式掌握这些模型能让你在竞赛中快速解题避免复杂的DP推导。4.1 排列、组合、阶乘这是基础中的基础必须熟练。排列数 A(n, m) n! / (n-m)!从n个不同元素中取出m个元素按顺序排列。组合数 C(n, m) n! / (m! * (n-m)!)从n个不同元素中取出m个元素构成一组不计顺序。重要性质C(n, m) C(n, n-m)C(n, m) C(n-1, m-1) C(n-1, m)杨辉三角/帕斯卡公式也是组合数DP求法的依据多重集的排列/组合元素有重复公式不同需注意。蓝桥杯常见考点直接套公式的题越来越少更多的是需要你识别出问题本质是某个组合模型。例如“隔板法”用于解决“将n个相同物品分给m个不同对象每个对象至少分得1个”的问题方案数为C(n-1, m-1)。4.2 卡特兰数括号匹配与出栈序列卡特兰数是一个在组合计数中频繁出现的数列。其递推公式为C(0)1, C(n1) Σ_{i0}^{n} C(i)*C(n-i)前几项为1, 1, 2, 5, 14, 42, 132...经典模型n对括号的合法匹配序列数C(n)。n个节点的不同二叉搜索树BST数量C(n)。一个栈的进栈序列为1,2,...,n不同的出栈序列数C(n)。在网格中从(0,0)走到(n,n)只能向右或向上且不穿过对角线即yx的路径数C(n)。实战应用当你看到题目描述符合上述任何一个模型时可以直接套用卡特兰数。计算时由于n可能很大通常需要结合组合数公式和取模运算来求。公式为C(n) C(2n, n) / (n1)。4.3 容斥原理解决“至少一个”或“交集”问题当问题要求“满足至少一个条件”或者多个条件之间有重叠时容斥原理是利器。公式对于n个集合A1, A2, ..., An则至少属于其中一个集合的元素个数为|A1∪A2∪...∪An| Σ|Ai| - Σ|Ai∩Aj| Σ|Ai∩Aj∩Ak| - ... (-1)^(n1)|A1∩A2∩...∩An|蓝桥杯例题求1到1000中能被2, 3, 5中至少一个整除的数的个数。设A为被2整除的集合B为被3整除C为被5整除。|A| 1000/2 500,|B| 333,|C| 200。|A∩B| 1000/lcm(2,3)1000/6166,|A∩C|1000/10100,|B∩C|1000/1566。|A∩B∩C| 1000/lcm(2,3,5)1000/3033。根据容斥原理|A∪B∪C| 500333200 - 166-100-66 33 734。我的踩坑心得容斥原理的难点在于“符号”和“求交集大小”。对于“至少满足一个条件”的问题用上述公式。对于“一个条件都不满足”的问题可以用总数减去“至少满足一个”的数量。求多个集合的交集大小时通常是求这些条件的最小公倍数LCM相关的整除个数。在编程实现时n个条件的容斥可以通过二进制枚举所有非空子集来实现非常方便。5. 实战拆解蓝桥杯真题“高僧斗法”的计数思维让我们分析一下你提供的热词中的一道真题蓝桥杯2013年第四届真题-高僧斗法。虽然这是一道博弈论尼姆游戏的题目但其解题过程中蕴含了深刻的“状态计数”和“转化”思想对于理解计数问题的灵活性很有帮助。题目简述回忆版在一条路上有n个石子堆代表高僧的位置两个玩家轮流操作。每次操作可以选择一个石子堆拿走至少一个石子。当所有石子堆的石子数都变成0时游戏结束。最后无法操作的人输。但本题有一个关键约束每次操作不能使石子数变为负数且操作后石子堆的石子数必须呈“严格递增”序列模拟高僧的法力高低。问先手是否有必胜策略。这不是一道直接的计数题但它如何与计数关联状态表示游戏的一个状态可以用一个有序元组(a1, a2, ..., an)来表示其中a1 a2 ... an。所有可能的状态构成了一个庞大的状态空间。胜负态计数思维层面博弈论DP的核心就是给每个状态标记“必胜态(N-position)”或“必败态(P-position)”。从终点状态全是0但不符合递增可视为游戏已结束的特殊状态倒推。一个状态是必败态当且仅当它的所有可能下一步操作到达的状态都是必胜态一个状态是必胜态当且仅当它存在至少一种操作可以走到一个必败态。从计数到优化如果直接对状态空间进行DP计数计算每个状态是N还是P状态数量是组合数级别的无法计算。这就需要利用博弈论的“SG函数”和“尼姆和”理论来优化。SG函数本身可以看作是对一个状态所代表的“游戏分支”的一种数学化“计数”和“归类”。将复杂的游戏转化为尼姆堆就是找到了一个等价计数模型。对备战计数问题的启示转化思想很多复杂的计数问题可以通过建模转化为已知的经典模型如组合数、DP、卡特兰数。这道题将“约束下的取石子游戏”转化为了“尼姆游戏”。状态压缩即使不能显式地枚举所有状态我们也可以通过分析状态的特征如奇偶性、模数、异或和来对状态进行“分类计数”从而得到通用解。在这道题中通过计算“阶梯尼姆”的异或和就能直接判断必胜必败而不需要知道具体有多少个必胜态。边界与约束题目中“严格递增”的约束是关键。在你自己设计DP状态时也常常需要加入类似的约束条件例如序列中相邻元素的差值、大小关系等来定义状态这会使状态转移方程更复杂但也是解题的突破口。6. 备赛训练策略与资源推荐理解了原理和模型还需要通过大量练习来内化。以下是我总结的备赛策略6.1 分阶段刷题计划第一阶段夯实基础1-2个月目标掌握加法/乘法原理、排列组合公式、简单DP爬楼梯、硬币、最长上升子序列。资源蓝桥杯官方练习系统的“基础练习”部分。LeetCode或洛谷的简单DP题、数学题。方法每个类型找5-10道题确保能独立、快速写出正确代码。重点理解状态定义和转移方程的推导过程而不是背代码。第二阶段模型突破2-3个月目标攻克区间DP、状态压缩DP、容斥原理、卡特兰数等核心模型。资源区间DP练习回文子序列、石子合并等问题。状态压缩DP练习棋盘放置如“蒙德里安的梦想”、“小国王”、旅行商问题(TSP)的计数变种。容斥原理练习求1-n中与m个数互质的数的个数、错排问题等。卡特兰数识别模型并练习大数取模下的计算。方法针对每个模型进行专项训练。总结该模型的状态定义套路、转移方程套路和初始化技巧。整理成自己的笔记。第三阶段真题模拟与综合训练1-2个月目标在时间压力下准确识别题目所属模型并快速实现。资源蓝桥杯历年真题省赛、国赛尤其是“计数”标签下的题目。方法卡时间4小时做整套真题。赛后重点复盘哪道题没想到模型哪道题实现出错了时间分配是否合理6.2 调试与优化技巧计数问题代码常见的BUG和优化点整数溢出这是最大的坑组合数、DP结果往往增长极快。蓝桥杯通常要求对结果取模如1e97。必须时刻警惕在可能发生乘法的任何地方先取模再运算。(a * b) % mod比a * b安全。使用long long类型C或Python的大整数。初始化错误DP数组的初始值至关重要。dp[0]或dp[0][0]往往代表“空方案”或“起点”通常是1。务必结合题意仔细思考。循环顺序错误特别是在二维/多维DP以及需要优化空间时如硬币组合问题。错误的循环顺序会导致状态被错误地重复计算或遗漏。记住一个原则在计算dp[i][j]时它所依赖的子状态必须已经被计算出来。模运算下的除法组合数公式中有除法如C(n, m) n! / (m! * (n-m)!)。在取模运算中不能直接做除法需要用到乘法逆元。通常使用费马小定理求逆元当模数为质数时a / b % mod a * pow(b, mod-2, mod) % mod。在比赛中可以预处理出阶乘数组fact[]和阶乘逆元数组inv_fact[]然后C(n,m) fact[n] * inv_fact[m] % mod * inv_fact[n-m] % mod。6.3 心理建设与考场策略先暴力再优化如果一时想不到完美的DP或公式先写一个暴力搜索DFS版本。这有两个好处一是可以验证小数据样例二是暴力搜索的递归树往往能给你提供状态设计的灵感。画图辅助对于DP问题在草稿纸上画出状态转移图哪怕只是简单的箭头能极大帮助你理清思路避免混乱。测试极端情况写完代码后务必测试n0,1等边界情况。对于计数问题这些地方最容易出错。时间管理如果一道计数题卡了超过30分钟还没有清晰思路先标记去做其他题。有时做完其他题再回头可能会有新灵感。备战蓝桥杯的“计数”专题本质上是在锻炼你的数学建模能力和逻辑组织能力。它要求你将一个模糊的实际问题抽象成清晰的数学关系然后用程序高效地计算出来。这个过程充满挑战但也极具乐趣。当你看到一道复杂的题目最终被简洁的状态转移方程或优雅的数学公式解决时那种成就感是无与伦比的。多思考、多总结、多动手你会发现“计数”不再是难题而是你竞赛武器库中一件得心应手的利器。