蓝桥杯超级玛丽详解：用一道题吃透动态规划核心思想-开发者社区

蓝桥杯练习系统的“算法提高VIP”栏目里，超级玛丽（题号1567）是我见过最朴素也最典型的动态规划题之一。题面没有复杂的图论、没有花哨的数据结构，核心就一句话：一条路、一堆障碍、每次跳一步或两步，问有多少种走法。可正是这样一道“入门级”的题，把DP的核心要素——状态、转移、初始化、边界处理——全考了一遍。无论你是刚开始备战蓝桥杯，还是学DP学得云里雾里，把这道题啃透，比刷十道同类型题都有用。

这道题我在训练系统里反复提交过好几次，第一次错在障碍坐标没处理干净，第二次错在没注意数据溢出，第三次才老老实实把滚动数组和边界情况一并理清。今天就把完整思路、代码实现和踩坑记录整理出来，给准备蓝桥杯的朋友一份可以照着复现的参考。

1. 题目场景还原：这道题的题面到底在讲什么

1.1 核心模型：从起点跳到终点的方案数

网上搜“蓝桥杯超级玛丽”，你可能会看到好几个版本的题面：有的说玛丽要过河，有的说路上有炮弹，还有的说是一次跳一个或两个石阶。措辞五花八门，但算法模型完全一致——数轴上有编号为1到n的位置，玛丽从位置1出发，目标是到达位置n。每次移动只能前进1步或2步，也就是从位置i只能走到i+1或i+2。路上有m个位置是障碍物，玛丽不能落在上面，问一共有多少种不同的走法。

举个例子，n=5，障碍在位置3，那么可行路径只有一条：1 → 2 → 4 → 5。为什么？因为1 → 3被障碍挡死，1 → 2 → 3也不允许，从2到4是跳2步，再到5是跳1步，整条路径唯一。这个例子的价值在于，它让你直观感受到“障碍物的存在会砍掉一整批候选路径”，而我们的算法必须精确统计剩下那些路径的数量。

1.2 输入输出格式与坐标约定

这道题在OJ上的标准输入格式大致如下：第一行两个正整数n和m，n是路径长度（也就是位置总数），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的方案数其实服从斐波那契数列的增长规律，n=10时约有89种，n=20时约10946种，n=30时已经超过134万种，n=50时轻松突破十亿级别。如果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]=1，dp[2]=1，dp[3]=2，dp[4]=3，dp[5]=5……每一项等于前两项之和。如果你画一条从起点逐步推进的线，会发现任何一条到达位置i的路径，最后一步只有两种可能：来自i-1的短跳，或来自i-2的长跳。这两种可能性互不重叠，加起来就是总数，不会重复也不会遗漏。这一步想通了，整个DP方程就没有任何悬念了。

2.3 加上障碍：状态转移的完整定义

现在把障碍物加回来。障碍物的含义是“这个位置不能落脚”，那么只要玛丽到达的位置是障碍，这条路径就必须作废。反映在状态上很简单：如果位置i是障碍，就令dp[i]=0，表示没有任何路径能到达这里。

所以完整的递推处理流程是：

读入n和m，开一个长度为n+2的dp数组，初始值全部为0。
用一个bool数组bad标记障碍位置，bad[i]=true表示位置i不可落脚。
初始化dp[1]=1，前提是位置1本身不是障碍（一般情况下起点不会是障碍，但代码里最好判断一下）。
从i=2到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]+0=1，正好对应“从位置1只能跳1步到位置2”这唯一一种情况。因此dp数组开成n+2，多出来的下界是安全的，不会访问越界。

为了验证这个方程的正确性，我们手动跑一遍n=5、障碍在位置3的例子：

dp[1]=1（起点）
位置2不是障碍，dp[2]=dp[1]+dp[0]=1+0=1
位置3是障碍，dp[3]=0
位置4不是障碍，dp[4]=dp[3]+dp[2]=0+1=1
位置5不是障碍，dp[5]=dp[4]+dp[3]=1+0=1

最终结果1，和前面的手工枚举完全一致。如果去掉障碍，n=5的结果应该是5，方程给出的dp[5]=dp[4]+dp[3]=3+2=5，同样正确。

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; vector<long long> dp(n + 2, 0); vector<bool> 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，因为斐波那契数列增长极快，n=50时答案已经超过万亿，int完全装不下。第二，读障碍位置时做了x>=1 && x<=n的区间判断，防止输入数据不干净导致数组越界。蓝桥杯的测试数据一般不会故意刁难，但养成这个习惯能省掉很多莫名其妙的运行时错误。

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同样能覆盖到n=90左右的范围，如果题目给的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: break

Python的int是无限精度的，所以完全不用操心溢出问题，写起来很省心。不过Python跑OJ时性能天然弱于C++，好在这题n最多几千，O(n)的复杂度不管什么语言都能轻松通过。如果你在Python组比赛，直接交这版就行。

4. 最容易踩坑的四个细节：从坐标到溢出

4.1 障碍坐标越界：读入时必须加区间判断

我第一次写这题，障碍数组直接bad[x]=true，没有判断x的合法性。当时测试数据全在范围内，样例通过了，以为稳了。后来换了一个数据版本，障碍物里出现了一个等于n+1的位置，程序直接运行时数组越界崩溃。有的OJ不会报错而是返回RE，排查起来特别浪费考试时间。

正确的姿势是读入障碍坐标后，先判断是否在1到n之间，不在范围内直接忽略。因为路径本身只涉及位置1到n，障碍物在范围外对方案数没有任何影响。这个判断一行代码的事，却能避免最危险的一类越界问题。

4.2 连续障碍与不可达区间

障碍物如果连续出现，某些位置会彻底变成死区，后续位置全部断掉。典型的例子是n=4，障碍在位置2和3。手动推一遍：dp[1]=1，dp[2]=0，dp[3]=0，dp[4]=dp[3]+dp[2]=0+0=0，答案就是0。因为任何路径一旦进入位置2或3就会踩雷，而没有其他绕路方式，所以终点必然不可达。

连续障碍是很多初学DP的人容易忽略的场景。他们只记得“障碍位置dp=0”，却忘了检查这条规则对后续递推的连锁反应。其实只要方程写对了，连续障碍的断流效果会自然体现，不需要额外特判。真正要小心的是另一种情况：如果障碍物分散且不连续，千万不要以为“跳过这个障碍就能继续”，还是要老老实实逐位置递推，让方程自己说话。

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的方案数，边界条件i==n时返回1，i>n或i是障碍时返回0，否则返回dfs(i+1)+dfs(i+2)，再用一个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+前缀和优化”的好素材。你只要把超级玛丽的代码扩展一下，加一个前缀和数组，就能轻松处理。