蓝桥杯里这道题如果你刷得够多应该会眼熟——名字叫“超级玛丽”又是那个红帽子水管工在跳跳跳但说白了就是一道跳格子方案数的题。很多第一次做它的同学容易被游戏外壳唬住以为要写个搜索甚至贪心实际上它是一道非常典型的计数型动态规划考的就是状态定义和转移方程的功力。题目编号1567归类在算法提高组的VIP题单里难度不算高但出现在备赛阶段的价值非常高只要啃下它后面遇到一大票“走路、跳台阶、过河”类的问题都能顺手解掉。这篇文章我会从题意拆解讲到底层转移方程的推导再到C、Java、Python三种语言的完整实现最后把我在调试时踩过的坑和考场上的经验一起整理出来适合正在备赛蓝桥杯、或者刚开始刷DP想找练手题的读者。1. 题目到底在说什么把游戏规则翻译成算法语言1.1 从超级玛丽到跳格子题面的本质题目套了一层游戏皮玛丽要从起点出发沿着一条路前进路上某些格子是陷阱不能踩踩到直接失败。她每次可以向前跳1格、2格或者3格问你从起点安全到达终点一共有多少种不同的跳法。去掉皮肤之后其实就是一个一维模型数轴上有n个位置标记为1到n某些位置不可停留从位置1出发每次只能向正方向移动1、2或3步问恰好停在位置n的方案总数。如果终点本身是个陷阱那没有任何方案输出0。把游戏规则翻译成算法语言的时候有几个细节特别容易看漏第一“只能往前走”意味着状态是单向的天然适合按顺序递推第二“跳1到3格”决定了每一步的步长集合是固定的第三“方案数”而不是“可行性”决定了我们做的是计数而不是布尔判断。这三个特征加在一起几乎就是在脸谱化地喊“快用动态规划”。1.2 输入输出与数据范围蓝桥杯的题目描述不同年份和语言版本的措辞会有细微差别但骨架基本一致。我以最常见的版本为例第一行给一个正整数n表示整条路一共有n个格子编号从1到n第二行给n个数每个数要么是0要么是11表示这个格子有陷阱0表示安全。玛丽从第1格出发要到达第n格输出跳法总数对某个模数取模后的结果常规题面里出现过10007这类小模数在蓝桥杯老题里非常常见如果题目没给模数就说明答案在数据类型能承受的范围内。数据范围上n一般不会太大常见到1000左右。这个规模意味着一维数组存DP状态绰绰有余连优化都不用做。但我也要提醒一句有些改编版数据范围会做到10^7以上这时候就必须上滚动数组后面我会专门讲。读题时先确认三件事起点是不是一定安全、终点是不是一定安全、模数是多少。这三件事直接影响代码的头尾写法比转移方程本身更容易让你丢分。2. 为什么是动态规划先试试深搜会怎样2.1 暴力枚举的思路与代价新手看到“有多少种方案”第一反应往往是搜索。思路也对从第1格出发每条路尝试跳1、2、3格跳过陷阱的格子搜到终点就计数加一。这个思路完全没错但是跑起来会发现它是指数级爆炸。画一下递归树就明白了玛丽在起点有3种选择每个选择之后又有3种选择树的深度大约是n/1到n/3之间。最多的情况下一棵三叉树的节点数能达到3的n次方级别。这个增长有多吓人n20的时候3^20大约是3.4亿基本上就已经跑不动了n50数字大到计算机直接原地放弃。就算你用DFS加剪枝把陷阱格下面的分支剪掉遇到一条全是安全格的路还是会被打回原形。我刚开始学DP的时候也干过这种傻事觉得搜索加上剪枝就能通吃所有计数题结果在OJ上看到超时的那一刻才意识到剪枝能剪掉的是显式的无效分支剪不掉的是重复子问题。2.2 重复子问题深搜慢的真正原因为什么深搜会重复计算我们来看一个小例子。假设n6从第1格出发路径1→2→4→6和1→3→4→6都经过了4这个格子。在第一条路径里我们已经算过“从4出发到6有几种走法”走到第二条路径的4时这个结果又要重新算一遍。“从第i格出发到达终点的方案数”这个值会被无数条前缀路径共用。每锁在一条具体的行走路径里它就会被重复计算一次。这就是动态规划出手的时刻把“从第i格往后走有几种方案”从路径中剥离出来单独存成数组让不同的前缀路径共享同一个计算结果。用状态来重组问题之后原问题就变成了到达第i格的安全方案数只依赖到达它前面1格、前面2格、前面3格的安全方案数。因为到达第i格的最后一步只有三种来源而且前面的行走过程是什么样、怎么走到前几格的完全不影响后面怎么跳。这种“过去不影响未来只影响当前值”的性质就是动态规划最核心的无后效性。3. 状态转移与边界核心推导3.1 状态定义与转移方程设计dp数组的时候我习惯把下标直接对应到格子的编号让语义一致。定义dp[i]为“从起点安全到达第i格的不同跳法总数”。这里有一种容易混淆的说法是“从i到终点”两种定义都能做但“从起点到i”更方便从左往右递推也更好和遍历逻辑对齐。转移方程写出来非常简洁dp[i] (dp[i-1] dp[i-2] dp[i-3]) % MOD前提是第i格本身不是陷阱。为什么只有三项因为玛丽最多跳3格要想恰好落在第i格最后一步只能是从第i-1、i-2或i-3格起跳不可能从更远的地方直接飞过来。三种来源互不重叠所以方案数直接相加。这个“来源于前k个状态”的框架也是斐波那契数列递推的推广版只是从加两项变成加三项。3.2 初始化与循环顺序初始化是整个递推里最容易出问题的一步。第1格是起点玛丽一开始就站在那所以dp[1]1。这里要强调一个直觉起点算不算一种方案答案是算。因为后续所有路径都从这一步继承下来如果不初始化成1整条链全是0最后输出自然是0。循环顺序必须是从小下标到大下标也就是从第2格一直算到第n格。原因很简单dp[i]依赖dp[i-1]、dp[i-2]、dp[i-3]如果倒着算算到i的时候它依赖的状态还没算出来整个递推就崩了。这一点说起来简单但在写滚动数组的时候特别容易手滑我会在第5节详细演示怎么处理。3.3 陷阱格与边界特判陷阱格的正确做法不是在转移的时候“跳过它”而是直接把dp[i]置为0。很多人写代码的时候会在加和时判断“如果i-k是陷阱就不加”这样做逻辑上凑得对但容易漏掉一种情况陷阱格自己作为落脚点。比如玛丽三步之内可以落到陷阱格这个位置被踩过就失败了所以任何经过它的路径都无效。与其在转移里逐个判断前驱是否安全不如先把dp[trap]清零这样后面计算引用它的时候自然就是0一步到位。边界情况需要单独拎出来讨论。第一如果起点本身就是陷阱玛丽没有任何站位直接输出0。第二如果n1且起点安全那么玛丽已经站在终点答案就是1这个现象很多新手想不明白总觉得“跳都没跳怎么算一种方案”其实在计数DP里初始状态本身就是一条完整的长度为0的路径。第三当i小于3的时候比如算dp[2]只有dp[1]可以用dp[0]不存在所以要加下标判断。也可以用“把数组多开3个格子下标从3开始映射”的办法把循环写得更清爽但新手还是建议先把朴素版写对再考虑下标平移。4. 完整代码实现三种语言一次讲透4.1 C 版本最直接的写法#include bits/stdc.h using namespace std; const int MOD 10007; const int MAXN 1005; int a[MAXN]; int dp[MAXN]; int main() { int n; cin n; for (int i 1; i n; i) { cin a[i]; } if (a[1] 1) { cout 0 endl; return 0; } dp[1] 1; for (int i 2; i n; i) { if (a[i] 1) { dp[i] 0; continue; } if (i - 1 1) { dp[i] (dp[i] dp[i - 1]) % MOD; } if (i - 2 1) { dp[i] (dp[i] dp[i - 2]) % MOD; } if (i - 3 1) { dp[i] (dp[i] dp[i - 3]) % MOD; } } cout dp[n] % MOD endl; return 0; }这段代码几个值得注意的细节数组a用来标记陷阱1表示陷阱dp数组清零后只初始化dp[1]。循环里先判断当前位置是不是陷阱是就直接跳过不是再累加前三个状态。取模放在每次加法之后防止溢出的同时也保证中间结果不会变得太大。对于蓝桥杯常见的10007模数就算不每步取模int也放得下但养成每步取模的习惯总归没错换到1e97的题也照样能跑。4.2 Java 版本注意输入和数组下标import java.util.Scanner; public class Main { static final int MOD 10007; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] a new int[n 1]; int[] dp new int[n 1]; for (int i 1; i n; i) { a[i] sc.nextInt(); } if (a[1] 1) { System.out.println(0); return; } dp[1] 1; for (int i 2; i n; i) { if (a[i] 1) { continue; } if (i - 1 1) { dp[i] (dp[i] dp[i - 1]) % MOD; } if (i - 2 1) { dp[i] (dp[i] dp[i - 2]) % MOD; } if (i - 3 1) { dp[i] (dp[i] dp[i - 3]) % MOD; } } System.out.println(dp[n] % MOD); } }Java版本和C几乎一一对应主要区别在输入和定义的写法。Java没有bits/stdc.h需要用Scanner或BufferedReader读入。在蓝桥杯系统里Java类的名字必须是Main这个千万别写错否则编译过了也判0分。我见过不少同学本地跑得好好的提交上去就是编译错误一查发现类名写了别的。另外Java的int类型对10007摸完再加三项不会溢出但如果你把MOD换到接近int上限的值就要考虑用long来累加。4.3 Python 版本写起来最舒服性能要留意MOD 10007 def solve(): n int(input()) a list(map(int, input().split())) a [0] a if a[1] 1: print(0) return dp [0] * (n 1) dp[1] 1 for i in range(2, n 1): if a[i] 1: continue for k in range(1, 4): if i - k 1: dp[i] (dp[i] dp[i - k]) % MOD print(dp[n] % MOD) if __name__ __main__: solve()Python版本的优势是代码短、逻辑清晰内层循环直接遍历k1到3把三次手动加法压缩成一个循环。这种方式在步长集合变大时特别有用比如改成“只能跳1、2、5格”只需要把range(1,4)换成给定的集合。但要注意Python的for循环开销比C大不少如果n超过10^6纯Python动态规划会略显吃力这时候可以考虑用列表推导或者转到PyPy提交。蓝桥杯对Python时长一般也给得比较宽松所以这个写法应付普通数据完全没问题。5. 常见坑与排查表考场上的命门5.1 五个最容易丢分的坑第一个坑是下标错位。题目如果用1到n编号数组大小就开n1如果用0到n-1编号循环范围和转移判断全部要跟着改。最怕的是题目描述里说“第1块石头”结果输入从0开始读然后你惯性用1号下标去对应第一块石头数据错位却浑然不觉。第二个坑是把陷阱格当普通格子在转移时硬加。有人写dp[i]的时候不管a[i]是不是1先把前面三项加完最后再置0。在只依赖前驱的DP里这样做会导致陷阱格的值被之后的状态引用等于变相让路径“穿过”了陷阱结果出错。第三个坑是忘记特判起点或终点的陷阱。起点陷阱好理解人没法站上去终点陷阱容易被忽略因为转移时会自然把dp[n]算出来如果陷阱置0的代码写在continue前面可能输出一个非零数。第四个坑是模数不统一。读题的时候没看清到底取不取模、取模数是几憋到写完代码才发现输出格式不对。我的建议是开局读题时就用笔把“输出要求”圈出来写代码前先确定常量。第五个坑是n1的输出问题。很多人在dp[1]1之后循环从2开始最后输出dp[n]也就是dp[1]看起来没错但如果你提前把a[1]1的特判写成了“起点陷阱输出0”那就没有歧义。如果忘了这个特判n1且第1格是陷阱的情况会输出dp[1]1错误非常隐蔽。我把这些坑整理成一张排查表方便考前快查症状可能原因正确做法小数据对大数据错没取模或取模时机不对每次加法后立即取模输出比预期小很多陷阱格被清零但引用它的前一个状态没连带处理先置dp[trap]0再转移输出比预期大没有跳过陷阱格路径穿墙在循环开头判断a[i]并跳过数组越界/异常i-2、i-3访问了负下标加下标判断或数组整体偏移n1时答案不对起点/终点陷阱特判缺失单独写a[1]1返回05.2 空间优化从O(n)到O(1)的滚动数组如果题目把n放大到百万甚至千万量级开一个n1的int数组有时候还是能扛的但蓝桥杯内存限制有时候给得抠门还要考虑dp数组和标记数组双份内存两百万个int就是8MB再翻倍可能捉襟见肘。这时候可以上滚动数组。因为dp[i]只依赖前三个状态所以只需要长度为4的数组就够用。关键技巧是用i % 4定位存储int roll[4] {0}; roll[1 % 4] 1; // 起点 for (int i 2; i n; i) { if (a[i] 1) { roll[i % 4] 0; continue; } int sum 0; for (int k 1; k 3; k) { if (i - k 1) { sum (sum roll[(i - k) % 4]) % MOD; } } roll[i % 4] sum; } cout roll[n % 4] endl;这里有一个思想陷阱你是在计算dp[i]的新值但roll[i % 4]可能还存着dp[i-4]的旧值所以必须先清零或者覆盖。上面代码在陷阱格的位置直接置0在安全格的位置用sum覆盖顺序上要注意不能在覆盖之前把旧值加到别处去。我刚开始写滚动数组时老出bug就是因为下意识以为数组下标i%4对应的就是“当前i的值”忽略了它同时可能是i-4的位置。6. 蓝桥杯实战怎么快速认出这题该用DP6.1 题干特征模式识别备赛刷题多了你会发现蓝桥杯的许多题都是同一种套路换了层皮。拿“超级玛丽”来总结识别计数型DP的几个信号词题干出现“多少种”、“方案数”、“不同的跳法”、“路线数量”行动规则有固定步长集“某某位置不能走/不能停”。一旦这三点同时出现大概率就是一道简单的线性动态规划。相反的如果题干问的是“能不能到达”、“最短几步”那就是另一个分支要么BFS求最短路要么用贪心或者动态规划求最值。同样是走路题考察点完全不同别看到“走路”就往方案数上套。在蓝桥杯的历年真题里和“超级玛丽”同宗同源的题非常多比如数字三角形、过河卒、摘花生、方格取数。它们的共同点都是“从起点到终点每个点有一个值或限制问最大/最小/方案数”。我自己的习惯是准备一个小本子把所有走路类DP的题按“问方案数、问最大值、求最短步数”三类归档考试时看到新题先查归类再套对应模板速度会快很多。6.2 考场上的几个加分习惯第一写代码前先在草稿纸上画一个小例子比如n6、陷阱在4手算出答案再用代码跑对不上就说明理解错了。这个习惯帮我抓住过至少五次边界错误。第二输出前一定要再看一眼题目要求的格式有的题多个空格都不行更不用说模数写错。第三把dp数组先全部初始化为0避免静态数组中残留的脏数据。蓝桥杯OJ上用的是Linux环境全局数组倒是默认0但保险起见显式清零又不费几行代码。另外我强烈推荐一个调试技巧写一个暴力DFS版来对拍。小数据n不超过20的时候暴力搜索能正确输出答案用rand生成一堆随机数据把暴力结果和DP结果对比自动找差异。这比人肉Debug快得多。我自己备赛时经常把对拍脚本留下来换一道新DP题把转移改改就能复用。6.3 扩展思考如果步长和规则变了怎么办把“超级玛丽”当作一个母题来看它的变形题在比赛中层出不穷。最经典的变化是把固定步长1到3改成“给定步长集合”比如只能跳2格和5格这时转移方程变成dp[i] sum(dp[i - k])其中遍历k属于步长集合而且注意如果某个步长会跳过终点那这条路径不合法。另一个常见变化是“第n格不一定要恰好到达”问“能走到超过终点吗”这类题的边界和转移就完全不同了需要额外处理终点之后的虚拟状态。还有的变化加入体力和代价变成哪种步长消耗多少体力问在限定体力内有多少方案那就得再开一维体力维度从线性DP进化到背包DP。我见过很多同学刷题只刷一道是一道从不总结母题变形。其实动态规划的学习最值钱的就是“母题—变式”的迁移能力。你把“超级玛丽”写透等于给“过河卒”、“跳台阶”、“走方格”这一整个家族打了底下次碰到它们只需要改改转移数组的长度和初始状态即可。我个人在实际操作中的体会是这类题的代码量真的不大C版本五十行顶天了但为什么蓝桥杯历年的通过率不高因为选手们普遍输在细节上要么边界特判漏了要么循环下标错了要么模数没取。刷题的时候宁可慢一点把每一行代码的语义都盘清楚尤其是dp[1]为什么等于1、陷阱格为什么置0这种问题别靠背要靠理解。等你想通“我到底在维护什么”超级玛丽这道题才真正变成送分题。 
长河君 · 2026/10/10 11:01:06 · 阅读 1.2k 蓝桥杯超级玛丽跳格子：动态规划解法与三种语言实现
蓝桥杯里这道题如果你刷得够多应该会眼熟——名字叫“超级玛丽”又是那个红帽子水管工在跳跳跳但说白了就是一道跳格子方案数的题。很多第一次做它的同学容易被游戏外壳唬住以为要写个搜索甚至贪心实际上它是一道非常典型的计数型动态规划考的就是状态定义和转移方程的功力。题目编号1567归类在算法提高组的VIP题单里难度不算高但出现在备赛阶段的价值非常高只要啃下它后面遇到一大票“走路、跳台阶、过河”类的问题都能顺手解掉。这篇文章我会从题意拆解讲到底层转移方程的推导再到C、Java、Python三种语言的完整实现最后把我在调试时踩过的坑和考场上的经验一起整理出来适合正在备赛蓝桥杯、或者刚开始刷DP想找练手题的读者。1. 题目到底在说什么把游戏规则翻译成算法语言1.1 从超级玛丽到跳格子题面的本质题目套了一层游戏皮玛丽要从起点出发沿着一条路前进路上某些格子是陷阱不能踩踩到直接失败。她每次可以向前跳1格、2格或者3格问你从起点安全到达终点一共有多少种不同的跳法。去掉皮肤之后其实就是一个一维模型数轴上有n个位置标记为1到n某些位置不可停留从位置1出发每次只能向正方向移动1、2或3步问恰好停在位置n的方案总数。如果终点本身是个陷阱那没有任何方案输出0。把游戏规则翻译成算法语言的时候有几个细节特别容易看漏第一“只能往前走”意味着状态是单向的天然适合按顺序递推第二“跳1到3格”决定了每一步的步长集合是固定的第三“方案数”而不是“可行性”决定了我们做的是计数而不是布尔判断。这三个特征加在一起几乎就是在脸谱化地喊“快用动态规划”。1.2 输入输出与数据范围蓝桥杯的题目描述不同年份和语言版本的措辞会有细微差别但骨架基本一致。我以最常见的版本为例第一行给一个正整数n表示整条路一共有n个格子编号从1到n第二行给n个数每个数要么是0要么是11表示这个格子有陷阱0表示安全。玛丽从第1格出发要到达第n格输出跳法总数对某个模数取模后的结果常规题面里出现过10007这类小模数在蓝桥杯老题里非常常见如果题目没给模数就说明答案在数据类型能承受的范围内。数据范围上n一般不会太大常见到1000左右。这个规模意味着一维数组存DP状态绰绰有余连优化都不用做。但我也要提醒一句有些改编版数据范围会做到10^7以上这时候就必须上滚动数组后面我会专门讲。读题时先确认三件事起点是不是一定安全、终点是不是一定安全、模数是多少。这三件事直接影响代码的头尾写法比转移方程本身更容易让你丢分。2. 为什么是动态规划先试试深搜会怎样2.1 暴力枚举的思路与代价新手看到“有多少种方案”第一反应往往是搜索。思路也对从第1格出发每条路尝试跳1、2、3格跳过陷阱的格子搜到终点就计数加一。这个思路完全没错但是跑起来会发现它是指数级爆炸。画一下递归树就明白了玛丽在起点有3种选择每个选择之后又有3种选择树的深度大约是n/1到n/3之间。最多的情况下一棵三叉树的节点数能达到3的n次方级别。这个增长有多吓人n20的时候3^20大约是3.4亿基本上就已经跑不动了n50数字大到计算机直接原地放弃。就算你用DFS加剪枝把陷阱格下面的分支剪掉遇到一条全是安全格的路还是会被打回原形。我刚开始学DP的时候也干过这种傻事觉得搜索加上剪枝就能通吃所有计数题结果在OJ上看到超时的那一刻才意识到剪枝能剪掉的是显式的无效分支剪不掉的是重复子问题。2.2 重复子问题深搜慢的真正原因为什么深搜会重复计算我们来看一个小例子。假设n6从第1格出发路径1→2→4→6和1→3→4→6都经过了4这个格子。在第一条路径里我们已经算过“从4出发到6有几种走法”走到第二条路径的4时这个结果又要重新算一遍。“从第i格出发到达终点的方案数”这个值会被无数条前缀路径共用。每锁在一条具体的行走路径里它就会被重复计算一次。这就是动态规划出手的时刻把“从第i格往后走有几种方案”从路径中剥离出来单独存成数组让不同的前缀路径共享同一个计算结果。用状态来重组问题之后原问题就变成了到达第i格的安全方案数只依赖到达它前面1格、前面2格、前面3格的安全方案数。因为到达第i格的最后一步只有三种来源而且前面的行走过程是什么样、怎么走到前几格的完全不影响后面怎么跳。这种“过去不影响未来只影响当前值”的性质就是动态规划最核心的无后效性。3. 状态转移与边界核心推导3.1 状态定义与转移方程设计dp数组的时候我习惯把下标直接对应到格子的编号让语义一致。定义dp[i]为“从起点安全到达第i格的不同跳法总数”。这里有一种容易混淆的说法是“从i到终点”两种定义都能做但“从起点到i”更方便从左往右递推也更好和遍历逻辑对齐。转移方程写出来非常简洁dp[i] (dp[i-1] dp[i-2] dp[i-3]) % MOD前提是第i格本身不是陷阱。为什么只有三项因为玛丽最多跳3格要想恰好落在第i格最后一步只能是从第i-1、i-2或i-3格起跳不可能从更远的地方直接飞过来。三种来源互不重叠所以方案数直接相加。这个“来源于前k个状态”的框架也是斐波那契数列递推的推广版只是从加两项变成加三项。3.2 初始化与循环顺序初始化是整个递推里最容易出问题的一步。第1格是起点玛丽一开始就站在那所以dp[1]1。这里要强调一个直觉起点算不算一种方案答案是算。因为后续所有路径都从这一步继承下来如果不初始化成1整条链全是0最后输出自然是0。循环顺序必须是从小下标到大下标也就是从第2格一直算到第n格。原因很简单dp[i]依赖dp[i-1]、dp[i-2]、dp[i-3]如果倒着算算到i的时候它依赖的状态还没算出来整个递推就崩了。这一点说起来简单但在写滚动数组的时候特别容易手滑我会在第5节详细演示怎么处理。3.3 陷阱格与边界特判陷阱格的正确做法不是在转移的时候“跳过它”而是直接把dp[i]置为0。很多人写代码的时候会在加和时判断“如果i-k是陷阱就不加”这样做逻辑上凑得对但容易漏掉一种情况陷阱格自己作为落脚点。比如玛丽三步之内可以落到陷阱格这个位置被踩过就失败了所以任何经过它的路径都无效。与其在转移里逐个判断前驱是否安全不如先把dp[trap]清零这样后面计算引用它的时候自然就是0一步到位。边界情况需要单独拎出来讨论。第一如果起点本身就是陷阱玛丽没有任何站位直接输出0。第二如果n1且起点安全那么玛丽已经站在终点答案就是1这个现象很多新手想不明白总觉得“跳都没跳怎么算一种方案”其实在计数DP里初始状态本身就是一条完整的长度为0的路径。第三当i小于3的时候比如算dp[2]只有dp[1]可以用dp[0]不存在所以要加下标判断。也可以用“把数组多开3个格子下标从3开始映射”的办法把循环写得更清爽但新手还是建议先把朴素版写对再考虑下标平移。4. 完整代码实现三种语言一次讲透4.1 C 版本最直接的写法#include bits/stdc.h using namespace std; const int MOD 10007; const int MAXN 1005; int a[MAXN]; int dp[MAXN]; int main() { int n; cin n; for (int i 1; i n; i) { cin a[i]; } if (a[1] 1) { cout 0 endl; return 0; } dp[1] 1; for (int i 2; i n; i) { if (a[i] 1) { dp[i] 0; continue; } if (i - 1 1) { dp[i] (dp[i] dp[i - 1]) % MOD; } if (i - 2 1) { dp[i] (dp[i] dp[i - 2]) % MOD; } if (i - 3 1) { dp[i] (dp[i] dp[i - 3]) % MOD; } } cout dp[n] % MOD endl; return 0; }这段代码几个值得注意的细节数组a用来标记陷阱1表示陷阱dp数组清零后只初始化dp[1]。循环里先判断当前位置是不是陷阱是就直接跳过不是再累加前三个状态。取模放在每次加法之后防止溢出的同时也保证中间结果不会变得太大。对于蓝桥杯常见的10007模数就算不每步取模int也放得下但养成每步取模的习惯总归没错换到1e97的题也照样能跑。4.2 Java 版本注意输入和数组下标import java.util.Scanner; public class Main { static final int MOD 10007; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] a new int[n 1]; int[] dp new int[n 1]; for (int i 1; i n; i) { a[i] sc.nextInt(); } if (a[1] 1) { System.out.println(0); return; } dp[1] 1; for (int i 2; i n; i) { if (a[i] 1) { continue; } if (i - 1 1) { dp[i] (dp[i] dp[i - 1]) % MOD; } if (i - 2 1) { dp[i] (dp[i] dp[i - 2]) % MOD; } if (i - 3 1) { dp[i] (dp[i] dp[i - 3]) % MOD; } } System.out.println(dp[n] % MOD); } }Java版本和C几乎一一对应主要区别在输入和定义的写法。Java没有bits/stdc.h需要用Scanner或BufferedReader读入。在蓝桥杯系统里Java类的名字必须是Main这个千万别写错否则编译过了也判0分。我见过不少同学本地跑得好好的提交上去就是编译错误一查发现类名写了别的。另外Java的int类型对10007摸完再加三项不会溢出但如果你把MOD换到接近int上限的值就要考虑用long来累加。4.3 Python 版本写起来最舒服性能要留意MOD 10007 def solve(): n int(input()) a list(map(int, input().split())) a [0] a if a[1] 1: print(0) return dp [0] * (n 1) dp[1] 1 for i in range(2, n 1): if a[i] 1: continue for k in range(1, 4): if i - k 1: dp[i] (dp[i] dp[i - k]) % MOD print(dp[n] % MOD) if __name__ __main__: solve()Python版本的优势是代码短、逻辑清晰内层循环直接遍历k1到3把三次手动加法压缩成一个循环。这种方式在步长集合变大时特别有用比如改成“只能跳1、2、5格”只需要把range(1,4)换成给定的集合。但要注意Python的for循环开销比C大不少如果n超过10^6纯Python动态规划会略显吃力这时候可以考虑用列表推导或者转到PyPy提交。蓝桥杯对Python时长一般也给得比较宽松所以这个写法应付普通数据完全没问题。5. 常见坑与排查表考场上的命门5.1 五个最容易丢分的坑第一个坑是下标错位。题目如果用1到n编号数组大小就开n1如果用0到n-1编号循环范围和转移判断全部要跟着改。最怕的是题目描述里说“第1块石头”结果输入从0开始读然后你惯性用1号下标去对应第一块石头数据错位却浑然不觉。第二个坑是把陷阱格当普通格子在转移时硬加。有人写dp[i]的时候不管a[i]是不是1先把前面三项加完最后再置0。在只依赖前驱的DP里这样做会导致陷阱格的值被之后的状态引用等于变相让路径“穿过”了陷阱结果出错。第三个坑是忘记特判起点或终点的陷阱。起点陷阱好理解人没法站上去终点陷阱容易被忽略因为转移时会自然把dp[n]算出来如果陷阱置0的代码写在continue前面可能输出一个非零数。第四个坑是模数不统一。读题的时候没看清到底取不取模、取模数是几憋到写完代码才发现输出格式不对。我的建议是开局读题时就用笔把“输出要求”圈出来写代码前先确定常量。第五个坑是n1的输出问题。很多人在dp[1]1之后循环从2开始最后输出dp[n]也就是dp[1]看起来没错但如果你提前把a[1]1的特判写成了“起点陷阱输出0”那就没有歧义。如果忘了这个特判n1且第1格是陷阱的情况会输出dp[1]1错误非常隐蔽。我把这些坑整理成一张排查表方便考前快查症状可能原因正确做法小数据对大数据错没取模或取模时机不对每次加法后立即取模输出比预期小很多陷阱格被清零但引用它的前一个状态没连带处理先置dp[trap]0再转移输出比预期大没有跳过陷阱格路径穿墙在循环开头判断a[i]并跳过数组越界/异常i-2、i-3访问了负下标加下标判断或数组整体偏移n1时答案不对起点/终点陷阱特判缺失单独写a[1]1返回05.2 空间优化从O(n)到O(1)的滚动数组如果题目把n放大到百万甚至千万量级开一个n1的int数组有时候还是能扛的但蓝桥杯内存限制有时候给得抠门还要考虑dp数组和标记数组双份内存两百万个int就是8MB再翻倍可能捉襟见肘。这时候可以上滚动数组。因为dp[i]只依赖前三个状态所以只需要长度为4的数组就够用。关键技巧是用i % 4定位存储int roll[4] {0}; roll[1 % 4] 1; // 起点 for (int i 2; i n; i) { if (a[i] 1) { roll[i % 4] 0; continue; } int sum 0; for (int k 1; k 3; k) { if (i - k 1) { sum (sum roll[(i - k) % 4]) % MOD; } } roll[i % 4] sum; } cout roll[n % 4] endl;这里有一个思想陷阱你是在计算dp[i]的新值但roll[i % 4]可能还存着dp[i-4]的旧值所以必须先清零或者覆盖。上面代码在陷阱格的位置直接置0在安全格的位置用sum覆盖顺序上要注意不能在覆盖之前把旧值加到别处去。我刚开始写滚动数组时老出bug就是因为下意识以为数组下标i%4对应的就是“当前i的值”忽略了它同时可能是i-4的位置。6. 蓝桥杯实战怎么快速认出这题该用DP6.1 题干特征模式识别备赛刷题多了你会发现蓝桥杯的许多题都是同一种套路换了层皮。拿“超级玛丽”来总结识别计数型DP的几个信号词题干出现“多少种”、“方案数”、“不同的跳法”、“路线数量”行动规则有固定步长集“某某位置不能走/不能停”。一旦这三点同时出现大概率就是一道简单的线性动态规划。相反的如果题干问的是“能不能到达”、“最短几步”那就是另一个分支要么BFS求最短路要么用贪心或者动态规划求最值。同样是走路题考察点完全不同别看到“走路”就往方案数上套。在蓝桥杯的历年真题里和“超级玛丽”同宗同源的题非常多比如数字三角形、过河卒、摘花生、方格取数。它们的共同点都是“从起点到终点每个点有一个值或限制问最大/最小/方案数”。我自己的习惯是准备一个小本子把所有走路类DP的题按“问方案数、问最大值、求最短步数”三类归档考试时看到新题先查归类再套对应模板速度会快很多。6.2 考场上的几个加分习惯第一写代码前先在草稿纸上画一个小例子比如n6、陷阱在4手算出答案再用代码跑对不上就说明理解错了。这个习惯帮我抓住过至少五次边界错误。第二输出前一定要再看一眼题目要求的格式有的题多个空格都不行更不用说模数写错。第三把dp数组先全部初始化为0避免静态数组中残留的脏数据。蓝桥杯OJ上用的是Linux环境全局数组倒是默认0但保险起见显式清零又不费几行代码。另外我强烈推荐一个调试技巧写一个暴力DFS版来对拍。小数据n不超过20的时候暴力搜索能正确输出答案用rand生成一堆随机数据把暴力结果和DP结果对比自动找差异。这比人肉Debug快得多。我自己备赛时经常把对拍脚本留下来换一道新DP题把转移改改就能复用。6.3 扩展思考如果步长和规则变了怎么办把“超级玛丽”当作一个母题来看它的变形题在比赛中层出不穷。最经典的变化是把固定步长1到3改成“给定步长集合”比如只能跳2格和5格这时转移方程变成dp[i] sum(dp[i - k])其中遍历k属于步长集合而且注意如果某个步长会跳过终点那这条路径不合法。另一个常见变化是“第n格不一定要恰好到达”问“能走到超过终点吗”这类题的边界和转移就完全不同了需要额外处理终点之后的虚拟状态。还有的变化加入体力和代价变成哪种步长消耗多少体力问在限定体力内有多少方案那就得再开一维体力维度从线性DP进化到背包DP。我见过很多同学刷题只刷一道是一道从不总结母题变形。其实动态规划的学习最值钱的就是“母题—变式”的迁移能力。你把“超级玛丽”写透等于给“过河卒”、“跳台阶”、“走方格”这一整个家族打了底下次碰到它们只需要改改转移数组的长度和初始状态即可。我个人在实际操作中的体会是这类题的代码量真的不大C版本五十行顶天了但为什么蓝桥杯历年的通过率不高因为选手们普遍输在细节上要么边界特判漏了要么循环下标错了要么模数没取。刷题的时候宁可慢一点把每一行代码的语义都盘清楚尤其是dp[1]为什么等于1、陷阱格为什么置0这种问题别靠背要靠理解。等你想通“我到底在维护什么”超级玛丽这道题才真正变成送分题。