蓝桥杯练习系统的“算法提高VIP”栏目里超级玛丽题号1567是我见过最朴素也最典型的动态规划题之一。题面没有复杂的图论、没有花哨的数据结构核心就一句话一条路、一堆障碍、每次跳一步或两步问有多少种走法。可正是这样一道“入门级”的题把DP的核心要素——状态、转移、初始化、边界处理——全考了一遍。无论你是刚开始备战蓝桥杯还是学DP学得云里雾里把这道题啃透比刷十道同类型题都有用。这道题我在训练系统里反复提交过好几次第一次错在障碍坐标没处理干净第二次错在没注意数据溢出第三次才老老实实把滚动数组和边界情况一并理清。今天就把完整思路、代码实现和踩坑记录整理出来给准备蓝桥杯的朋友一份可以照着复现的参考。1. 题目场景还原这道题的题面到底在讲什么1.1 核心模型从起点跳到终点的方案数网上搜“蓝桥杯 超级玛丽”你可能会看到好几个版本的题面有的说玛丽要过河有的说路上有炮弹还有的说是一次跳一个或两个石阶。措辞五花八门但算法模型完全一致——数轴上有编号为1到n的位置玛丽从位置1出发目标是到达位置n。每次移动只能前进1步或2步也就是从位置i只能走到i1或i2。路上有m个位置是障碍物玛丽不能落在上面问一共有多少种不同的走法。举个例子n5障碍在位置3那么可行路径只有一条1 → 2 → 4 → 5。为什么因为1 → 3被障碍挡死1 → 2 → 3也不允许从2到4是跳2步再到5是跳1步整条路径唯一。这个例子的价值在于它让你直观感受到“障碍物的存在会砍掉一整批候选路径”而我们的算法必须精确统计剩下那些路径的数量。1.2 输入输出格式与坐标约定这道题在OJ上的标准输入格式大致如下第一行两个正整数n和mn是路径长度也就是位置总数m是障碍物的数量。第二行有m个整数表示障碍物所在的位置编号。数据范围在不同版本里略有差异但基本都在n不超过几百到一千的量级障碍物数量m通常也不大。输出就是一个整数表示从位置1到达位置n的跳法总数。这里要提醒一句有些题面会把起点写成位置0、终点写成位置n有些则用位置1到n。本质上就是把整个数轴平移一个单位代码里的初始化方式稍有不同但递推逻辑一模一样。本文统一采用“位置1为起点、位置n为终点”的约定后面的所有推导和代码都基于这个约定。如果你在别的OJ上碰到0起点的版本只需要把dp[0]1改成dp[0]1并把循环从1开始逻辑是等价的。1.3 为什么这道题值得认真做作为“算法提高VIP”栏目的题目超级玛丽其实没有用到任何高深算法它考察的是最基础的DP建模能力。但正因为基础它的可迁移性极强爬楼梯、过河、跳格子、硬币凑数甚至一些状态机DP底层都是类似的“线性递推障碍限制”结构。我当时刷这道题最大的收获不是学会了斐波那契数列而是学会了“先明确状态含义再列方程最后才写代码”的思考顺序。很多初学者一看到题就想写递归或者搜索结果n一大人就麻了。这篇博文后面会专门对比暴力枚举和DP的差异你就能理解为什么DP是这个场景下的正解。2. 方案数从哪来状态定义与递推方程的完整推导2.1 先看暴力枚举为什么不可行碰到“求方案数”的题第一反应往往是枚举所有路径。这条路虽然直观但代价极大。在没有障碍的情况下玛丽在绝大多数位置都有两种选择跳1步或跳2步。路径总数会随着n的增长呈现指数级膨胀。算一下就知道到达位置i的方案数其实服从斐波那契数列的增长规律n10时约有89种n20时约10946种n30时已经超过134万种n50时轻松突破十亿级别。如果n给到100暴力枚举所有路径根本不可能在比赛时间内跑完。更麻烦的是路径本身还要一条条判断是否踩到障碍这又增加了额外的开销。所以这道题注定不能用“生成所有路径再筛选”的思路。真正靠谱的做法是动态规划不枚举路径而是把“到达某个位置的方案数”记录下来用前一个位置和前两个位置的方案数累加得到当前位置的方案数。这就是典型的“用空间换时间”也是DP最核心的思想——重叠子问题的复用。2.2 从斐波那契数列说起先把障碍物全部忽略问题就变成从位置1出发每次走1步或2步到达位置n有多少种走法这个简化版模型和斐波那契数列几乎是一回事。设dp[i]表示到达位置i的方案总数。因为玛丽只能从i-1跳1步过来或者从i-2跳2步过来所以到达i的方案数恰好等于到达i-1的方案数加上到达i-2的方案数即dp[i] dp[i-1] dp[i-2]。壳子换了一下本质就是斐波那契数列dp[1]1dp[2]1dp[3]2dp[4]3dp[5]5……每一项等于前两项之和。如果你画一条从起点逐步推进的线会发现任何一条到达位置i的路径最后一步只有两种可能来自i-1的短跳或来自i-2的长跳。这两种可能性互不重叠加起来就是总数不会重复也不会遗漏。这一步想通了整个DP方程就没有任何悬念了。2.3 加上障碍状态转移的完整定义现在把障碍物加回来。障碍物的含义是“这个位置不能落脚”那么只要玛丽到达的位置是障碍这条路径就必须作废。反映在状态上很简单如果位置i是障碍就令dp[i]0表示没有任何路径能到达这里。所以完整的递推处理流程是读入n和m开一个长度为n2的dp数组初始值全部为0。用一个bool数组bad标记障碍位置bad[i]true表示位置i不可落脚。初始化dp[1]1前提是位置1本身不是障碍一般情况下起点不会是障碍但代码里最好判断一下。从i2到n依次计算dp[i]如果i是障碍dp[i]0否则dp[i]dp[i-1]dp[i-2]。最终答案就是dp[n]。这里有个细节值得注意dp[0]没有实际意义但在计算dp[2]时会用到dp[1]dp[0]。因为dp[0]保持0所以dp[2]dp[1]01正好对应“从位置1只能跳1步到位置2”这唯一一种情况。因此dp数组开成n2多出来的下界是安全的不会访问越界。为了验证这个方程的正确性我们手动跑一遍n5、障碍在位置3的例子dp[1]1起点位置2不是障碍dp[2]dp[1]dp[0]101位置3是障碍dp[3]0位置4不是障碍dp[4]dp[3]dp[2]011位置5不是障碍dp[5]dp[4]dp[3]101最终结果1和前面的手工枚举完全一致。如果去掉障碍n5的结果应该是5方程给出的dp[5]dp[4]dp[3]325同样正确。3. 代码落地C、Java、Python三种实现与边界处理3.1 C实现最直观的数组版本C是蓝桥杯最主流的参赛语言代码写起来也最接近底层思路。下面这份实现直接照搬上面的递推方程障碍判断、起点特判都做了可以直接拿去OJ上提交。#include iostream #include vector using namespace std; int main() { int n, m; // 有些题面是多组测试数据可以套一层 while (cin n m) cin n m; vectorlong long dp(n 2, 0); vectorbool bad(n 2, false); for (int i 0; i m; i) { int x; cin x; if (x 1 x n) { bad[x] true; } } // 起点如果是障碍直接无解 if (bad[1]) { cout 0 endl; return 0; } dp[1] 1; for (int i 2; i n; i) { if (bad[i]) { dp[i] 0; continue; } dp[i] dp[i - 1] dp[i - 2]; } cout dp[n] endl; return 0; }这段代码里有两个地方值得反复确认。第一dp用long long而不是int因为斐波那契数列增长极快n50时答案已经超过万亿int完全装不下。第二读障碍位置时做了x1 xn的区间判断防止输入数据不干净导致数组越界。蓝桥杯的测试数据一般不会故意刁难但养成这个习惯能省掉很多莫名其妙的运行时错误。3.2 Java实现注意OJ环境与Scanner的取舍蓝桥杯练习系统的Java环境通常是Java 8提交类名必须叫Main。很多人第一次用Java写这道题会因为Scanner读取多组数据的方式不对而卡住这里我给出一个稳妥的写法。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); while (sc.hasNextInt()) { int n sc.nextInt(); int m sc.nextInt(); boolean[] bad new boolean[n 2]; for (int i 0; i m; i) { int x sc.nextInt(); if (x 1 x n) { bad[x] true; } } if (bad[1]) { System.out.println(0); continue; } long[] dp new long[n 2]; dp[1] 1; for (int i 2; i n; i) { if (bad[i]) { continue; } dp[i] dp[i - 1] dp[i - 2]; } System.out.println(dp[n]); } sc.close(); } }这段代码用了hasNextInt去判断是否还有下一组输入万一题面改成多组数据也能正确应对。虽然这道题绝大多数版本只有一组输入但写成循环并不会影响正确性反而更保险。Java的long同样能覆盖到n90左右的范围如果题目给的n更大就得换BigInteger不过蓝桥杯算法提高里的这个题long基本够用。3.3 Python实现代码最短但要注意输入终止Python写这题最简洁但有个坑OJ上用input()读多组数据时容易EOFError。蓝桥杯虽然主推C/C和Java但也开了Python组所以这里也放一版。while True: try: n, m map(int, input().split()) bad [False] * (n 2) for x in map(int, input().split()): if 1 x n: bad[x] True if bad[1]: print(0) continue dp [0] * (n 2) dp[1] 1 for i in range(2, n 1): if bad[i]: continue dp[i] dp[i - 1] dp[i - 2] print(dp[n]) except EOFError: breakPython的int是无限精度的所以完全不用操心溢出问题写起来很省心。不过Python跑OJ时性能天然弱于C好在这题n最多几千O(n)的复杂度不管什么语言都能轻松通过。如果你在Python组比赛直接交这版就行。4. 最容易踩坑的四个细节从坐标到溢出4.1 障碍坐标越界读入时必须加区间判断我第一次写这题障碍数组直接bad[x]true没有判断x的合法性。当时测试数据全在范围内样例通过了以为稳了。后来换了一个数据版本障碍物里出现了一个等于n1的位置程序直接运行时数组越界崩溃。有的OJ不会报错而是返回RE排查起来特别浪费考试时间。正确的姿势是读入障碍坐标后先判断是否在1到n之间不在范围内直接忽略。因为路径本身只涉及位置1到n障碍物在范围外对方案数没有任何影响。这个判断一行代码的事却能避免最危险的一类越界问题。4.2 连续障碍与不可达区间障碍物如果连续出现某些位置会彻底变成死区后续位置全部断掉。典型的例子是n4障碍在位置2和3。手动推一遍dp[1]1dp[2]0dp[3]0dp[4]dp[3]dp[2]000答案就是0。因为任何路径一旦进入位置2或3就会踩雷而没有其他绕路方式所以终点必然不可达。连续障碍是很多初学DP的人容易忽略的场景。他们只记得“障碍位置dp0”却忘了检查这条规则对后续递推的连锁反应。其实只要方程写对了连续障碍的断流效果会自然体现不需要额外特判。真正要小心的是另一种情况如果障碍物分散且不连续千万不要以为“跳过这个障碍就能继续”还是要老老实实逐位置递推让方程自己说话。4.3 答案溢出long long不是万能保险斐波那契数列的膨胀速度远超直觉。F(50)大约是125亿F(90)已经接近2.88×10^18刚好卡在long long的边界附近。如果题目把n给到100甚至更大long long也会溢出此时必须换方案。蓝桥杯这道题在不同版本的OJ上n的范围不太一样有的很小只有三五十有的可能到几百。我在本地测试时习惯先看一眼n的最大值再决定数据类型n在90以内用long long稳稳的n超过90就考虑Java的BigInteger或者Python的int。C选手遇到大n的大数场景比较痛苦但好消息是这道题在蓝桥杯练习系统里n通常不大long long能过。我的建议是写代码之前先扫一眼数据范围养成习惯别等溢出错了才回头改。4.4 起点和终点是障碍时需要特判正常题目里起点和终点不会是障碍物因为题面已经明确“从一端跳到另一端”落脚点不可能设在坑里。但OJ的测试数据偶尔会有边界情况万一bad[1]true那么根本没法出发答案直接是0。如果不特判dp[1]1的初始化会把错误结果一直带到最后导致输出一个不该出现的正数。我在代码里加了if (bad[1])输出0这个特判成本极低却能把一类隐蔽错误直接堵死。终点是障碍的情况不用单独处理因为循环递推到n时bad[n]true会让dp[n]0方程已经自动覆盖了。5. 从超级玛丽出发滚动数组、跳k步与求最少步数5.1 滚动数组从O(n)空间降到O(1)超级玛丽这题n不大开数组无所谓。但如果你在竞赛里碰到n达到百万级别的同类题数组方案就显得奢侈了。观察递推方程dp[i]dp[i-1]dp[i-2]每一时刻真正用到的只有前两项所以完全可以用两个变量滚动替换。long long prev1 1; // dp[1] long long prev2 0; // dp[0]实际无意义保持0 for (int i 2; i n; i) { long long cur; if (bad[i]) cur 0; else cur prev1 prev2; prev2 prev1; prev1 cur; } cout prev1 endl;注意这里prev1在循环结束后就是dp[n]prev2是dp[n-1]。滚动数组虽然省空间可读性和调试便利性会下降所以我建议初学者先写数组版本理解透了再考虑优化。考试的时候空间不紧张就尽量不要为了炫技增加出错概率。5.2 记忆化搜索另一种等价写法有一部分同学对递推循环不敏感反而对递归更熟。记忆化搜索本质上是同一个状态转移方程只是用递归自顶向下算。思路是定义函数dfs(i)表示从位置i到达终点n的方案数边界条件in时返回1in或i是障碍时返回0否则返回dfs(i1)dfs(i2)再用一个memo数组记录已经算过的结果。这个写法和递推是数学等价的理解起来更符合人的直觉但递归深度受n限制n过大会爆栈。超级玛丽的数据规模下递归完全可行也是很多教程推荐的入门写法。我个人建议如果你打算长期打算法竞赛老老实实掌握递推循环因为递归写法的常数更大后续遇到复杂题时容易拖慢节奏。但如果你是初学者记忆化搜索能帮助你建立“状态”和“转移”的直觉先用它入门再切换到循环并不丢人。5.3 变形题1每次可以跳k步如果你把“每次跳1步或2步”改成“每次跳1到k步中的任意步数”递推方程变成dp[i]dp[i-1]dp[i-2]...dp[i-k]障碍位置仍然是dp[i]0。这个版本不再等价于斐波那契数列而是变成了一个“滑动窗口求和”问题。朴素写法时间复杂度是O(nk)当k很大时不够用可以用前缀和把求和优化到O(1)整体变成O(n)。这个变体在蓝桥杯里不常考但它是理解“线性DP前缀和优化”的好素材。你只要把超级玛丽的代码扩展一下加一个前缀和数组就能轻松处理。5.4 变形题2不计数而是求最少步数超级玛丽问“有多少种方案”如果题目改成“最少需要多少次跳跃才能到达终点”思路就从DP方案数切换成了最短路径/贪心问题。因为每一步有1和2两种长度目标是最小化步数逻辑上优先跳2步会更省次数但障碍物的存在可能打乱这个节奏。这种变体更推荐用BFS或带状态的DP来做状态含义从“方案数”变成“到达该位置的最小步数”转移方程用min而不是加号。虽然和超级玛丽有关系但思考方向已经完全不同。刷题的时候要注意区分“计数类DP”和“最优化DP”两者的转移写法不能混淆。“超级玛丽”这个题最值得玩味的地方就是它身上延伸出的每一条线都能接住一个更大的算法知识点。我刷完这道题之后把同样的状态设计思路套到爬楼梯、过河、铺地砖这些经典题上明显感觉到自己“建模”的肌肉变强了。对于蓝桥杯备考来说与其匆匆刷完一百道题什么都不剩不如挑几道像这样的典型题目彻底吃透。