1. 从“进击的青蛙”看动态规划的经典入门最近在整理蓝桥杯的练习题翻到了ALGO-965这道题题目名字挺有意思叫“进击的青蛙”。乍一看可能会联想到一些跳跃游戏但本质上这是一道非常经典的动态规划入门题。如果你刚开始接触算法竞赛或者对动态规划DP还心存畏惧觉得它抽象又复杂那么从这道题入手会是一个绝佳的选择。它没有复杂的背景故事规则清晰状态转移直接能让你清晰地感受到DP的核心思想——将大问题分解为小问题并记住这些小问题的解避免重复计算。这道题描述了一个典型的“路径计数”场景一只青蛙站在一个数轴的原点位置0它每次可以向右跳1格、2格或3格。现在数轴上有一些位置被标记为“陷阱”青蛙不能跳到这些位置上。题目会给定数轴的总长度N终点位置以及所有陷阱的位置我们需要计算出青蛙从起点0跳到终点N有多少种不同的跳跃方案。这听起来是不是很像我们小时候做的“爬楼梯”问题经典的爬楼梯问题是每次可以走1步或2步问走到第n阶有多少种走法。而“进击的青蛙”可以看作是“爬楼梯”问题的升级版步长扩展到了3步并且加入了“障碍物”陷阱的限制。这个小小的变化就让问题从简单的斐波那契数列递推变成了需要结合条件判断的状态转移非常适合用来理解带约束的DP。2. 问题核心状态定义与转移方程的推导解决任何动态规划问题第一步也是最关键的一步就是定义“状态”。状态就是我们用来描述问题某个阶段情况的“快照”。对于这道题最自然的状态定义就是dp[i]表示青蛙跳到位置i时有多少种不同的跳跃方案。这里i的取值范围是从0到N。我们最终要求的就是dp[N]的值。定义了状态接下来就要找出状态之间是如何转移的也就是推导状态转移方程。青蛙是怎么跳到位置i的呢它只能从i-1、i-2或i-3这三个位置跳过来因为它的步长最大是3。所以跳到i的方案数就等于跳到i-1、i-2、i-3这三个位置的方案数之和。前提是这些位置是青蛙可以到达的即不是陷阱。于是我们可以得到初步的状态转移方程dp[i] dp[i-1] dp[i-2] dp[i-3]但这只是一个基础框架。我们还需要融入题目的约束条件陷阱位置如果位置i是陷阱那么青蛙根本不能站在这里所以dp[i]应该直接等于0。在计算后续位置时这个0值也会参与求和表示“无法从这个陷阱位置跳出去”。边界条件这是最容易出错的地方。我们需要明确dp[0]的值。青蛙一开始就站在位置0。那么“跳到位置0”这个事件本身算一种方案吗在路径计数问题中通常我们将起点视为一种“初始状态”即有一种方案使得青蛙位于起点。所以dp[0] 1。但这里有一个至关重要的细节位置0本身也可能是陷阱吗题目通常不会这么设置否则游戏无法开始但严谨的代码应该处理这种情况如果0是陷阱那么dp[0] 0整个方案数直接就是0。下标越界当i很小时比如i1i-3就变成了-2这是没有意义的。因此在求和时我们需要判断i-1,i-2,i-3是否大于等于0只对有效的下标进行累加。综合以上我们可以梳理出完整的解题逻辑初始化一个长度为N1的数组dp所有值设为0。用一个布尔数组trap标记陷阱位置trap[i] true表示i是陷阱。设置初始状态如果位置0不是陷阱则dp[0] 1否则为0。从i 1开始遍历到N如果i是陷阱dp[i] 0直接继续下一个位置。如果i不是陷阱则dp[i] (dp[i-1] if i-10 else 0) (dp[i-2] if i-20 else 0) (dp[i-3] if i-30 else 0)。注意结果可能很大通常题目会要求对某个大数如1000000007取模需要在每次加法后立即取模防止溢出。2.1 一个具体的计算实例假设N 5陷阱位置为[2, 4]。初始化dp [0, 0, 0, 0, 0, 0],trap[2]true,trap[4]true。初始状态0不是陷阱所以dp[0] 1。数组变为[1, 0, 0, 0, 0, 0]。开始迭代i1: 不是陷阱。dp[1] dp[0] 1。数组[1, 1, 0, 0, 0, 0]。i2: 是陷阱。dp[2] 0。数组[1, 1, 0, 0, 0, 0]。i3: 不是陷阱。dp[3] dp[2] dp[1] dp[0] 0 1 1 2。数组[1, 1, 0, 2, 0, 0]。i4: 是陷阱。dp[4] 0。数组[1, 1, 0, 2, 0, 0]。i5: 不是陷阱。dp[5] dp[4] dp[3] dp[2] 0 2 0 2。最终结果dp[5] 2。我们可以手动验证一下从0到5避开2和4的路径 路径1: 0 - 1 - 3 - 5 路径2: 0 - 3 - 5 确实只有两条。这个计算过程清晰地展示了DP是如何利用之前的结果一步步推导出最终答案的。3. 代码实现与关键细节剖析理解了原理代码实现就是水到渠成的事情。这里我用Python来演示因为其语法清晰易于理解算法本质。MOD 1000000007 # 常见的取模值 def solve(N, traps): :param N: 终点位置 :param traps: 陷阱位置列表 :return: 从0跳到N的方案数对MOD取模 # 初始化dp数组和陷阱标记数组 dp [0] * (N 1) is_trap [False] * (N 1) for pos in traps: if pos N: # 陷阱位置可能超过N但无关紧要 is_trap[pos] True # 边界条件处理 if is_trap[0]: return 0 # 起点就是陷阱无解 dp[0] 1 # 状态转移 for i in range(1, N 1): if is_trap[i]: dp[i] 0 # 当前位置是陷阱不可达 continue # 从i-1, i-2, i-3三个位置转移过来注意下标不能小于0 total 0 if i - 1 0: total (total dp[i - 1]) % MOD if i - 2 0: total (total dp[i - 2]) % MOD if i - 3 0: total (total dp[i - 3]) % MOD dp[i] total return dp[N] % MOD # 示例使用上一节的例子 N 5 traps [2, 4] print(solve(N, traps)) # 输出应为 2这段代码虽然短小但有几个细节值得深入探讨这些细节往往是竞赛中失分的坑点细节一取模运算的时机注意我们在累加total时每次加法后都立即% MOD。为什么不等到最后再取模呢因为中间累加的结果可能会非常大超出编程语言中整型的表示范围即使在Python中大整数虽然不会溢出但取模后运算更快且符合题目要求“对结果取模”的语义。这是一个非常好的编程习惯尤其是在C/Java等语言中可以避免意料之外的整数溢出。细节二陷阱数组的初始化与判断我们创建了一个长度为N1的布尔数组is_trap默认所有位置都不是陷阱False然后将给定的陷阱位置标记为True。这里有一个潜在的优化如果陷阱数量M远小于N我们可以用集合set来存储陷阱位置这样判断i in trap_set的平均时间复杂度是O(1)。但在最坏情况下几乎每个位置都是陷阱集合的性能可能反而不如数组的直接索引访问。对于本题的数据范围使用数组标记通常是更稳妥和清晰的选择。细节三关于dp数组的初始化大小dp数组的长度是N1这是因为我们要表示从位置0到位置N包含的所有状态。下标i直接对应位置i。这种“状态与下标直接对应”的DP通常称为“线性DP”是最容易理解和实现的一种。细节四空间复杂度的优化细心的你可能发现了在计算dp[i]时我们只依赖dp[i-1],dp[i-2],dp[i-3]。也就是说我们并不需要保存从0到N的所有历史状态只需要保存最近的3个状态。因此我们可以将空间复杂度从 O(N) 优化到 O(1)。这在N非常大比如上亿时是必要的。优化后的代码使用几个变量滚动更新def solve_optimized(N, traps): MOD 1000000007 is_trap [False] * (N 1) for pos in traps: if pos N: is_trap[pos] True if is_trap[0]: return 0 # 使用三个变量代表 dp[i-3], dp[i-2], dp[i-1] # 初始时i1, 那么 i-3-2(不存在记为0), i-2-1(不存在记为0), i-10 a, b, c 0, 0, 1 # 分别对应 dp[i-3], dp[i-2], dp[i-1] current 0 # dp[i] for i in range(1, N 1): if is_trap[i]: current 0 else: current (a b c) % MOD # 滚动更新变量为下一个i做准备 a, b, c b, c, current return current % MOD这个优化版本中a, b, c就像是一个滑动窗口始终保持着计算当前位置所需的前三个状态。在循环结束时current即c就是dp[N]的值。这是一个非常经典的DP空间优化技巧在解决“爬楼梯”及其变种问题时非常有用。4. 从本题延伸动态规划的常见变体与思维训练“进击的青蛙”是一个完美的教学案例掌握了它你可以轻松解决一大批同类型问题。更重要的是你可以通过修改它的条件来训练自己定义状态和推导方程的能力。我建议你尝试思考以下变体并动手实现变体一步长集合变化如果青蛙不是只能跳1、2、3格而是能跳的步长用一个数组steps [s1, s2, ..., sk]给出。那么转移方程就变为dp[i] sum(dp[i - step] for step in steps if i - step 0)这要求我们使用一个循环来遍历所有可能的步长。这实际上变成了一个“完全背包”问题步长是物品可以无限次使用位置i是背包容量求装满背包的方案数。变体二加入“连续跳跃限制”假设青蛙不能连续两次跳相同的步长例如如果这次跳了2格下一次就不能再跳2格。这时我们的状态定义就需要扩展必须包含“上一次跳跃的步长”这个信息。状态可以定义为dp[i][last_step]表示跳到位置i且上一次跳跃步长为last_step的方案数。状态转移时就需要从所有last_step ! step的状态转移过来。这引入了“状态机”的DP模型难度上了一个台阶。变体三求“最小跳跃次数”如果不求方案数而求从起点到终点的最少跳跃次数并且要避开陷阱。这就变成了一个典型的“最短路径”问题可以用BFS广度优先搜索来解决。因为每一步的代价都是1跳一次BFS第一次到达终点时的路径长度就是最短跳跃次数。这也说明了不同的问题描述计数 vs. 最优解会导致完全不同的算法选择。变体四路径输出如果题目不仅要求方案数还要求输出所有具体的跳跃路径。那么DP就不再适用了因为DP只记录数量不记录具体路径。我们需要使用DFS深度优先搜索或BFS来遍历所有可能的路径并在过程中记录路径。这通常会导致指数级的时间复杂度所以只适用于N较小的情况。通过对比这些变体你会发现动态规划的核心在于状态定义。状态必须包含足够的信息能够唯一确定当前局面并且能够从之前的状态推导出来。对于“进击的青蛙”原题位置i就是足够的信息。但对于变体二光知道位置就不够了还必须知道上一步怎么跳的否则无法判断下一步的合法性。5. 在竞赛中的实战技巧与避坑指南在蓝桥杯等限时竞赛中解决这类题目不仅要算法正确还要追求快速、稳定地写出代码。结合这道题我分享几个实战中的技巧和容易踩的坑技巧一先处理特殊情况和边界在开始写核心DP循环之前先把所有特殊情况处理掉。比如终点N就是陷阱直接返回0。起点0是陷阱直接返回0。N等于0青蛙不需要跳就在终点算一种方案前提是0不是陷阱返回1。 把这些情况写在最前面可以让核心逻辑更清晰也避免在DP循环中做复杂的条件判断。技巧二使用“记忆化搜索”作为思考起点如果你觉得直接推导递推式从底向上有点绕可以尝试“记忆化搜索”从上到下。写一个递归函数dfs(pos)表示从位置pos跳到终点N的方案数。那么如果pos N返回1到达终点算一种方案。如果pos是陷阱或者pos N返回0非法状态。否则dfs(pos) dfs(pos1) dfs(pos2) dfs(pos3)。 然后用一个数组memo存储计算过的dfs(pos)结果避免重复递归。这个思路非常直观几乎就是题目描述的直译。在竞赛中你可以先用这个思路确保问题理解正确然后再将其转化为更高效的递推DP。对于本题记忆化搜索的代码同样简洁。避坑一整数溢出与取模这是最最常见的错误。题目中往往不会直接说“结果可能很大请对1000000007取模”但会在数据范围中暗示。比如N最大为10^5方案数可能是一个天文数字。只要题目没有明确说结果在64位整数范围内或者数据范围很大就要下意识地考虑取模。取模运算要满足(a b) % MOD (a % MOD b % MOD) % MOD所以我们在每一步加法后取模是安全的。避坑二数组下标越界在DP循环中访问dp[i-1],dp[i-2],dp[i-3]时必须确保下标0。虽然像Python中负数下标有特殊含义会引发错误但在C/Java中访问负下标会导致未定义行为或运行时错误非常危险。稳妥的做法是在访问前加判断或者对i1,2进行特殊处理。在我的示例代码中通过if i-1 0这样的判断来规避。避坑三初始化陷阱数组时的范围陷阱位置列表traps中的值有可能大于N。在初始化is_trap数组时如果直接is_trap[pos] True而pos N就会导致数组索引越界。所以需要加上判断if pos N。虽然大于N的陷阱不影响青蛙的路径青蛙跳不到那里但程序不能因此崩溃。避坑四对“方案数”初始值的理解dp[0] 1还是dp[0] 0这需要结合具体问题理解。在这类“路径计数”问题中我们把“已经站在起点”视为一种初始的、唯一的方案。所以通常设为1。你可以这样想如果终点就是起点N0那么青蛙不需要跳就完成了任务这算1种方案。这个初始值直接影响整个递推的基数务必确认清楚。这道“进击的青蛙”虽然简单但它像一块璞玉几乎包含了线性DP的所有核心要素。把它吃透再遇到类似的题目比如“解码方法”、“不同路径”、“爬楼梯的最小成本”等等你都会有一种似曾相识的感觉。算法的学习就是这样通过攻克一个个经典的模型逐渐积累起解决复杂问题的能力。下次再看到青蛙在格子上跳来跳去你就能立刻看穿它动态规划的本质了。