企业官网建设流程全解析

蓝桥杯里这道题，如果你刷得够多，应该会眼熟——名字叫“超级玛丽”，又是那个红帽子水管工在跳跳跳，但说白了就是一道跳格子方案数的题。很多第一次做它的同学容易被游戏外壳唬住，以为要写个搜索甚至贪心，实际上它是一道非常典型的计数型动态规划，考的就是状态定义和转移方程的功力。题目编号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要么是1，1表示这个格子有陷阱，0表示安全。玛丽从第1格出发，要到达第n格，输出跳法总数对某个模数取模后的结果（常规题面里出现过10007，这类小模数在蓝桥杯老题里非常常见，如果题目没给模数，就说明答案在数据类型能承受的范围内）。

数据范围上，n一般不会太大，常见到1000左右。这个规模意味着一维数组存DP状态绰绰有余，连优化都不用做。但我也要提醒一句：有些改编版数据范围会做到10^7以上，这时候就必须上滚动数组，后面我会专门讲。读题时先确认三件事：起点是不是一定安全、终点是不是一定安全、模数是多少。这三件事直接影响代码的头尾写法，比转移方程本身更容易让你丢分。

2. 为什么是动态规划：先试试深搜会怎样

2.1 暴力枚举的思路与代价

新手看到“有多少种方案”，第一反应往往是搜索。思路也对：从第1格出发，每条路尝试跳1、2、3格，跳过陷阱的格子，搜到终点就计数加一。这个思路完全没错，但是跑起来会发现它是指数级爆炸。

画一下递归树就明白了：玛丽在起点有3种选择，每个选择之后又有3种选择，树的深度大约是n/1到n/3之间。最多的情况下一棵三叉树的节点数能达到3的n次方级别。这个增长有多吓人？n=20的时候，3^20大约是3.4亿，基本上就已经跑不动了；n=50，数字大到计算机直接原地放弃。就算你用DFS加剪枝，把陷阱格下面的分支剪掉，遇到一条全是安全格的路还是会被打回原形。

我刚开始学DP的时候也干过这种傻事，觉得搜索加上剪枝就能通吃所有计数题，结果在OJ上看到超时的那一刻才意识到：剪枝能剪掉的是显式的无效分支，剪不掉的是重复子问题。

2.2 重复子问题：深搜慢的真正原因

为什么深搜会重复计算？我们来看一个小例子。假设n=6，从第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。第二，如果n=1，且起点安全，那么玛丽已经站在终点，答案就是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也放得下，但养成每步取模的习惯总归没错，换到1e9+7的题也照样能跑。

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版本的优势是代码短、逻辑清晰，内层循环直接遍历k=1到3，把三次手动加法压缩成一个循环。这种方式在步长集合变大时特别有用，比如改成“只能跳1、2、5格”，只需要把range(1,4)换成给定的集合。但要注意，Python的for循环开销比C++大不少，如果n超过10^6，纯Python动态规划会略显吃力，这时候可以考虑用列表推导或者转到PyPy提交。蓝桥杯对Python时长一般也给得比较宽松，所以这个写法应付普通数据完全没问题。

5. 常见坑与排查表：考场上的命门

5.1 五个最容易丢分的坑

第一个坑是下标错位。题目如果用1到n编号，数组大小就开n+1；如果用0到n-1编号，循环范围和转移判断全部要跟着改。最怕的是题目描述里说“第1块石头”，结果输入从0开始读，然后你惯性用1号下标去对应第一块石头，数据错位却浑然不觉。

第二个坑是把陷阱格当普通格子在转移时硬加。有人写dp[i]的时候不管a[i]是不是1，先把前面三项加完，最后再置0。在只依赖前驱的DP里，这样做会导致陷阱格的值被之后的状态引用，等于变相让路径“穿过”了陷阱，结果出错。

第三个坑是忘记特判起点或终点的陷阱。起点陷阱好理解，人没法站上去；终点陷阱容易被忽略，因为转移时会自然把dp[n]算出来，如果陷阱置0的代码写在continue前面，可能输出一个非零数。

第四个坑是模数不统一。读题的时候没看清到底取不取模、取模数是几，憋到写完代码才发现输出格式不对。我的建议是开局读题时就用笔把“输出要求”圈出来，写代码前先确定常量。

第五个坑是n=1的输出问题。很多人在dp[1]=1之后，循环从2开始，最后输出dp[n]也就是dp[1]，看起来没错，但如果你提前把a[1]==1的特判写成了“起点陷阱输出0”，那就没有歧义。如果忘了这个特判，n=1且第1格是陷阱的情况会输出dp[1]=1，错误非常隐蔽。

我把这些坑整理成一张排查表，方便考前快查：

5.2 空间优化：从O(n)到O(1)的滚动数组

如果题目把n放大到百万甚至千万量级，开一个n+1的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. 蓝桥杯实战：怎么快速认出这题该用DP

6.1 题干特征模式识别

备赛刷题多了，你会发现蓝桥杯的许多题都是同一种套路换了层皮。拿“超级玛丽”来总结，识别计数型DP的几个信号词：题干出现“多少种”、“方案数”、“不同的跳法”、“路线数量”；行动规则有固定步长集；“某某位置不能走/不能停”。一旦这三点同时出现，大概率就是一道简单的线性动态规划。

相反的，如果题干问的是“能不能到达”、“最短几步”，那就是另一个分支，要么BFS求最短路，要么用贪心或者动态规划求最值。同样是走路题，考察点完全不同，别看到“走路”就往方案数上套。

在蓝桥杯的历年真题里，和“超级玛丽”同宗同源的题非常多，比如数字三角形、过河卒、摘花生、方格取数。它们的共同点都是“从起点到终点，每个点有一个值或限制，问最大/最小/方案数”。我自己的习惯是准备一个小本子，把所有走路类DP的题按“问方案数、问最大值、求最短步数”三类归档，考试时看到新题先查归类，再套对应模板，速度会快很多。

6.2 考场上的几个加分习惯

第一，写代码前先在草稿纸上画一个小例子，比如n=6、陷阱在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这种问题，别靠背，要靠理解。等你想通“我到底在维护什么”，超级玛丽这道题才真正变成送分题。