1. 项目概述从一道算法题看动态规划的实战拆解最近在整理蓝桥杯的备赛笔记翻到了ALGO-965这道名为“进击的青蛙”的题目。这名字起得挺有意思让人联想到一只小青蛙在格子间奋力跳跃的场景。实际上这是一道非常经典的动态规划入门题也是很多同学在初次接触“递推”思想时遇到的第一个小坎。它不涉及复杂的数据结构核心考察的就是你能否将问题抽象成状态并找到状态之间的转移关系。今天我就结合这道题把动态规划从思路到代码实现的完整链条拆开揉碎了讲一遍尤其是其中容易踩坑的边界处理和初始化逻辑这些往往是解题报告里一笔带过但实际编码时却让人头疼不已的地方。这道题描述了一个典型的线性路径问题青蛙站在一个标号为1的起点想要跳到标号为N的终点。中间有一些格子是“陷阱”不能停留。青蛙每次可以向前跳1格、2格或3格。我们的任务就是计算出青蛙从起点安全跳到终点的总方案数。题目会给定N的值以及陷阱格子的位置。理解了这个场景我们就能把它映射到动态规划的经典模型上——爬楼梯问题的变种。但别急直接套公式肯定会出问题因为“陷阱”这个约束条件让简单的递推公式变得需要小心翼翼。2. 问题核心与数学模型抽象2.1 问题重述与关键约束我们先抛开“青蛙”这个有趣的比喻把问题还原成更通用的描述。我们有一条从1到N的线性序列可以想象成一条数轴上的整数点。有一个“物体”初始位于点1每次移动可以向右移动1、2或3个单位长度。序列中的某些点被标记为“禁止停留点”。目标是计算从点1移动到点N且中途不经过任何“禁止停留点”的所有可能路径的数量。这里有几个至关重要的约束条件直接决定了我们算法的正确性起点和终点起点1和终点N默认是安全的可以停留。即使题目没说这也是隐含条件否则问题无解。移动方式每次移动的步长是离散的、确定的123。这限制了状态转移的来源。禁止点这是核心约束。路径不能“经过”禁止点这里的“经过”通常指的是“停留”。因为青蛙跳的过程是瞬时的我们只关心它最终落在哪个格子。所以只要它最终落脚的格子不是禁止点即可。这意味着禁止点只是不能作为跳转的“目标点”但青蛙的跳跃轨迹“跨过”禁止点是被允许的。这一点理解偏差会导致完全错误的递推关系。大数处理方案数可能非常巨大通常会要求对某个大数如1000000007取模这是算法竞赛的常规操作防止整数溢出。2.2 动态规划状态定义面对这类“计数”问题动态规划是首选武器。第一步也是最重要的一步就是定义“状态”。最直接的想法是设dp[i]表示“从起点1跳到位置i且不经过任何禁止点”的方案总数。这个定义是清晰且正确的。i就是我们的状态变量代表了青蛙所在的位置。dp[i]存储了到达这个状态的所有可能方式的数量。2.3 状态转移方程推导定义了状态接下来就要找状态之间的关系也就是递推公式。思考青蛙怎么跳到位置i的根据移动规则它只能从i-1,i-2,i-3这三个位置跳过来前提是这些位置存在且大于等于1。因此跳到i的方案数应该是跳到i-1、i-2、i-3的方案数之和。因为从这些位置再跳一步相应步长为1、2、3就能到达i。所以在没有禁止点的情况下朴素的转移方程是dp[i] dp[i-1] dp[i-2] dp[i-3]现在加入禁止点的约束。如果位置i本身是一个禁止点那么青蛙根本不能停留在这里所以到达这里的方案数应该是0。我们有两种处理方式在计算完dp[i]后如果发现i是禁止点强行将dp[i]设为0。更优雅的方式在转移之前就判断。只有当i不是禁止点时我们才计算dp[i]的值如果i是禁止点我们直接令dp[i] 0并且不利用它去更新后续状态因为从禁止点出发的跳跃是不允许的。此外我们还需要考虑i-1,i-2,i-3这些“前驱状态”是否合法。如果某个前驱位置是禁止点那么dp[前驱]本身就是0从该前驱转移过来的贡献也就是0这符合逻辑。所以我们只需要确保在累加时对于不存在的下标如i-3当i2时做好边界处理即可。因此加入禁止点判断后的核心转移逻辑如下# 假设 banned 是一个布尔数组banned[i]为True表示i是禁止点 if not banned[i]: # 只有当前位置不是陷阱才计算方案数 dp[i] 0 if i-1 1: dp[i] dp[i-1] if i-2 1: dp[i] dp[i-2] if i-3 1: dp[i] dp[i-3] dp[i] % MOD # 取模防止溢出 else: dp[i] 0 # 当前位置是陷阱方案数为02.4 初始化——一切开始的基石动态规划必须有一个起点。我们的状态定义是从1跳到i那么dp[1]表示从1跳到1的方案数这显然只有一种方案不动。所以dp[1] 1。但这里有一个巨大的坑我们需要根据位置1是否是禁止点来设置吗题目通常保证起点不是禁止点但严谨起见我们应该判断如果banned[1]为真那么问题无解直接输出0。否则dp[1] 1。对于dp[2]和dp[3]呢它们不能完全依赖上述的通用转移方程因为下标可能越界。我们需要手动初始化dp[2]可以从1跳1步过来。所以如果位置2不是禁止点则dp[2] dp[1]否则为0。dp[3]可以从1跳2步过来也可以从2跳1步过来。所以dp[3] dp[1] dp[2]前提是位置3不是禁止点。实操心得初始化的艺术很多同学在这里出错是因为试图用同一个循环从1计算到N然后对前几项做特殊判断逻辑容易混乱。我个人的习惯是单独处理前3个位置的初始化。这样代码逻辑更清晰。也可以采用“虚拟原点”的技巧即把dp数组下标从0开始令dp[0]1并认为从0跳到1、2、3有对应的关系这样可以统一转移方程。但作为初学者先理解分开初始化的方式更稳妥。3. 算法实现与代码精讲理解了原理我们来看代码实现。我会用Python作为示例语言因为它语法清晰贴近伪代码易于理解。3.1 输入处理与数据结构选择首先我们需要读取题目输入。通常格式是第一行两个整数N和M分别表示终点编号和陷阱数量。第二行M个整数表示陷阱的位置。MOD 1000000007 def solve(): import sys input sys.stdin.read data input().split() idx 0 N int(data[idx]); idx 1 M int(data[idx]); idx 1 # 创建陷阱标记数组下标从1开始到N方便对应 banned [False] * (N 1) # banned[0]无用 for _ in range(M): trap_pos int(data[idx]); idx 1 if 1 trap_pos N: # 防御性编程确保陷阱位置在有效范围内 banned[trap_pos] True # 如果起点或终点就是陷阱直接输出0 if banned[1] or banned[N]: print(0) return # dp数组初始化 dp [0] * (N 1) dp[1] 1 # 起点 # 手动初始化dp[2]和dp[3] if N 2: dp[2] 0 if banned[2] else dp[1] if N 3: if not banned[3]: dp[3] dp[1] (0 if banned[2] else dp[2]) else: dp[3] 0 # 状态转移 for i in range(4, N 1): if banned[i]: dp[i] 0 else: dp[i] (dp[i-1] dp[i-2] dp[i-3]) % MOD print(dp[N] % MOD) if __name__ __main__: solve()3.2 代码逐行解析与避坑指南输入读取使用sys.stdin.read()一次性读取所有输入再分割比多次调用input()在算法竞赛中更高效。陷阱数组banned列表长度为N1使得下标i直接对应位置i。banned[0]空置不用。这是一个以空间换清晰度的常见做法。起点终点检查这是一个非常重要的边界条件。即使题目数据可能保证起点终点不是陷阱自己加上这个判断能使程序更健壮逻辑更完整。dp数组初始化dp[1]固定为1。对于dp[2]和dp[3]的初始化代码中加入了if N 2和if N 3的判断。这是因为当N很小比如N1时直接访问dp[2]会导致下标越界。这是第二个容易忽略的坑。状态转移循环从i4开始到N结束。对于每个位置i先判断是否为陷阱。如果不是则从三个前驱状态求和并取模如果是则直接赋值为0。注意即使i是陷阱我们仍然需要为dp[i]赋值为0因为后面的状态i1,i2在计算时可能会用到dp[i]虽然贡献为0。取模操作在加和之后立即取模可以保证中间结果不会超出整型的表示范围。这是处理大数问题的标准操作。注意事项为什么循环内判断陷阱位置有同学可能会想先初始化整个dp数组然后把陷阱位置的dp值设为0不就行了吗这样在转移时就不需要判断了。这样做理论上是可行的但需要注意如果某个位置是陷阱那么它不应该为后续位置提供方案数。在我们的转移方程dp[i] dp[i-1] dp[i-2] dp[i-3]中如果i-1是陷阱dp[i-1]已经是0所以没问题。因此两种方式等价。在循环内判断逻辑更直白地体现了“只有非陷阱位置才计算方案数”这一思想。4. 测试与调试用案例验证逻辑任何算法代码都需要经过多种情况的测试。我们设计几个测试用例来验证程序的正确性。测试用例1基础功能测试输入 5 1 3解释N5有一个陷阱在3。手动计算路径1-2-4-51-2-51-4-5 (注意1-3-? 不行因为3是陷阱不能停留1-2-3-? 也不行) 所以方案数应为3。 程序输出应为3。测试用例2包含大数取模输入 1000 0解释N1000没有陷阱。这就是经典的“三步爬楼梯”问题。方案数会非常大程序应能正确计算并取模。我们可以用一个小脚本验证前几项dp[1]1, dp[2]1, dp[3]2, dp[4]4, dp[5]7, dp[6]13... 规律是dp[i]dp[i-1]dp[i-2]dp[i-3]。程序应对大N也能快速运行。测试用例3起点或终点是陷阱输入 5 2 1 5解释起点1和终点5都是陷阱。青蛙无法开始或结束旅程。程序应输出0。这测试了我们的边界检查逻辑。测试用例4N很小的情况输入 1 0解释N1起点即终点。方案数应为1不动。这测试了初始化部分对N1的处理是否会导致数组越界。测试用例5连续陷阱输入 6 3 2 3 4解释陷阱在2,3,4。可能的路径必须跳过这些区域。从1出发跳3步到4不行4是陷阱。跳2步到3不行。跳1步到2不行。 似乎无路可走等等青蛙可以跳3格1-44是陷阱不能作为落脚点。但题目通常允许“跨越”陷阱。那么1直接跳3步到4但4不能停所以这个动作无效。实际上从1只能尝试跳更远但最大步长是3。所以1无法到达任何非陷阱点5和6。让我们看看 唯一可能1跳3步到4禁止跳2步到3禁止跳1步到2禁止。所以没有合法路径到达5或6。但题目要去终点6。所以方案数为0。 这个案例测试了算法在连续陷阱下的处理能力。运行我们的程序这些测试用例都应该通过。如果某个用例失败就需要回头检查对应的逻辑块比如初始化、转移条件或者边界判断。5. 算法优化与空间压缩上面的解法时间复杂是O(N)空间复杂度也是O(N)对于题目给定的常规约束N可能到10^5或10^6是完全足够的。但如果我们想追求极致的空间效率或者N非常大时可以进行空间压缩。观察状态转移方程dp[i]只依赖于dp[i-1],dp[i-2],dp[i-3]。也就是说我们不需要保存整个dp数组只需要保存最近的三个状态即可。这就是经典的“滚动数组”优化。优化后的代码框架def solve_optimized(): # ... 输入读取和banned数组创建与之前相同 ... if banned[1] or banned[N]: print(0) return # 初始化前三个状态 if N 1: print(1) return # 用三个变量代替数组 a, b, c 1, 0, 0 # a代表dp[i-3], b代表dp[i-2], c代表dp[i-1]初始对应于i1的情况 # 手动计算dp[2]和dp[3]并更新a,b,c # 这里需要小心处理因为b和c的初始值需要根据位置2和3是否是陷阱来确定 # 为了清晰我们可以先按原始方法计算到dp[3]再开始滚动 # 方法还是先用列表算前3项再进入滚动循环。这样逻辑更清晰。 dp [0] * (N 1) dp[1] 1 if N 2: dp[2] 0 if banned[2] else dp[1] if N 3: dp[3] 0 if banned[3] else (dp[1] (0 if banned[2] else dp[2])) if N 3: print(dp[N] % MOD) return # 初始化滚动变量 a, b, c dp[1], dp[2], dp[3] # 分别对应i-3, i-2, i-1 # 从i4开始滚动 for i in range(4, N 1): if banned[i]: current 0 else: current (a b c) % MOD # 滚动更新a, b, c b, c, current a, b, c b, c, current print(c % MOD) # 循环结束时c保存的是dp[N]实操心得空间优化的权衡滚动数组优化将空间复杂度从O(N)降到了O(1)这在某些内存极其受限的场景下很有用。但是它牺牲了代码的一部分清晰度调试起来也更麻烦因为你不能方便地打印整个dp数组来查看状态。在竞赛或面试中如果时间允许先写出清晰的标准DP解法再提及可以优化空间是一个更稳妥的策略。除非题目明确要求O(1)空间否则优先保证正确性和可读性。6. 常见问题与思维延伸6.1 为什么是动态规划而不是搜索很多同学第一反应是用深度优先搜索DFS来模拟青蛙的所有跳跃路径。对于较小的N比如N30这确实可行。但当N增大到成千上万时DFS的指数级时间复杂度会立刻导致超时。动态规划通过记录子问题的解到达每个位置的方案数避免了重复计算将时间复杂度降到了线性O(N)。这是典型的用空间换时间也是动态规划的核心价值。6.2 如果步长集合变化怎么办原题中步长是固定的{1, 2, 3}。如果步长变成一个数组steps例如{1, 3, 5}算法如何调整 状态转移方程需要修改为dp[i] 0 for step in steps: if i - step 1 and not banned[i]: dp[i] dp[i-step]这增加了内层循环时间复杂度变为O(N * K)其中K是步长集合的大小。只要K不大算法依然高效。6.3 如果路径不是线性的而是图呢这是更一般的扩展。如果青蛙不是在线性序列上跳而是在一个图上每个节点有若干条出边代表可以跳到的下一个位置某些节点是陷阱。那么问题就变成了计算从起点节点到终点节点的所有路径数不经过陷阱节点。这依然可以用动态规划在DAG上或BFS结合记忆化搜索来解决但状态定义可能变为dp[node]表示从起点到节点node的方案数。6.4 取模的时机和常见错误取模运算(a b) % MOD满足(a % MOD b % MOD) % MOD。我们在每次加法后立即取模和最后再取模在数学上是等价的只要不涉及乘法溢出。立即取模的好处是始终保持数值在较小范围内避免中间结果溢出。特别是在Python中虽然整数可以很大但立即取模是个好习惯在其他语言如C、Java中则是必须的。一个常见错误是dp[i] dp[i-1] dp[i-2] dp[i-3] % MOD。注意取模运算符%的优先级高于加法所以这行代码等价于dp[i] dp[i-1] dp[i-2] (dp[i-3] % MOD)这显然不是我们想要的对总和取模。正确的写法是dp[i] (dp[i-1] dp[i-2] dp[i-3]) % MOD用括号确保先求和再取模。6.5 初始化dp[0]的技巧在一些解法和讨论中你会看到有人设置dp[0] 1并将起点视为位置1。这样dp[1]可以从dp[0]跳1步得到dp[2]可以从dp[0]跳2步和dp[1]跳1步得到以此类推。这样可以使转移方程从i1开始就统一为dp[i] dp[i-1] dp[i-2] dp[i-3]但需要仔细处理下标偏移和陷阱判断陷阱数组也要相应调整。这种方法更数学化但可能增加一层理解负担。我个人的建议是在理解基础版本之后再研究这种技巧作为思维拓展。这道“进击的青蛙”虽然只是一道基础的动态规划题但它清晰地展示了从问题分析、状态定义、转移方程推导、边界处理到代码实现的完整闭环。其中关于陷阱的处理、初始化细节以及取模运算都是算法实现中实实在在的“坑”。下次再遇到类似的线性递推计数问题比如“解码方法”、“爬楼梯变种”、“网格路径计数带障碍”你都可以尝试套用这个分析框架定义状态、寻找转移、处理边界、注意约束。把这些基础打牢了再去挑战更复杂的背包问题、树形DP、状态压缩DP才会更有底气。