1. 项目概述从一道经典DP题切入蓝桥杯国赛备战最近在带几个学生冲刺蓝桥杯国赛发现很多同学在动态规划DP这个坎上总是绕不过去尤其是遇到带障碍的变种题目思路就容易乱。今天我们就拿LeetCode上那道经典的“不同路径 II”来开刀这题在蓝桥杯的历年真题和模拟题里出现过各种“变装”核心就是考察带障碍的网格DP以及如何用滚动数组进行空间优化。如果你对“遇到障碍物怎么处理”、“dp数组怎么初始化”、“为什么可以用一维数组”这些问题还心存疑惑那这篇笔记就是为你准备的。我会从最朴素的二维DP思路开始一步步推导到最优的空间优化方案并分享一些在国赛高压环境下快速识别此类题目、避免踩坑的实战心得。这道题本身描述很简单一个机器人位于一个 m x n 网格的左上角每次只能向下或者向右移动一步试图到达右下角。但网格中有些格子设置了障碍物用1表示机器人不能进入。问总共有多少条不同的路径这直接对应了蓝桥杯中常见的“方案计数”类问题是理解DP思想一个非常好的载体。我们不仅要算出答案更要理解状态定义、转移方程背后的逻辑以及优化技巧的适用场景这才是冲刺国赛应有的深度。2. 核心思路拆解状态定义与转移方程的构建逻辑2.1 为什么是动态规划—— 问题性质的判断拿到任何一道算法题尤其是蓝桥杯这种时间紧迫的比赛第一步必须是快速判断题型。“不同路径 II”几乎把DP的特性写在了脸上第一求的是“总共有多少种路径”这是一个计数问题通常涉及累加符合DP的“计数型”应用场景。第二机器人的移动有非常强的“方向性”限制只能向右或向下这意味着到达某个格子(i, j)的路径只可能从它的上方(i-1, j)或者左方(i, j-1)过来。这种“当前状态仅由有限个前驱状态决定”的性质是DP的“最优子结构”特征。第三在计算(i, j)时我们会反复用到(i-1, j)和(i, j-1)的值存在“重叠子问题”。这三条合在一起动态规划就是最自然且高效的解法。这里有一个关键的思维定式需要打破很多新手一看到网格、路径就想用深度优先搜索DFS去暴力枚举。对于小规模网格比如20x20以内DFS或许能跑出结果。但蓝桥杯国赛的题目m和n轻松上百路径数是指数级增长的DFS必然超时。DP将指数复杂度降到了多项式级别O(m*n)这是质变。所以在赛场上看到网格路径计数首先就该在脑海里敲响DP的警钟。2.2 二维DP数组的定义与初始化陷阱最直观的思路是定义一个二维数组dp[i][j]表示从起点(0, 0)走到格子(i, j)的不同路径数量。我们的目标是求dp[m-1][n-1]。状态转移方程几乎可以脱口而出如果当前格子(i, j)不是障碍物那么到达这里的路径数等于从上面来的路径数加上从左边来的路径数。即dp[i][j] dp[i-1][j] dp[i][j-1]如果(i, j)是障碍物那么显然一条路都没有dp[i][j] 0。难点和坑点往往集中在初始化上。初始化是为状态转移提供正确的“起点”或“边界条件”。第一行i0和第一列j0的初始化这是最容易出错的地方。因为机器人只能向右或向下走所以对于第一行的任何格子(0, j)它只能从它的左边(0, j-1)过来不可能从上方来因为没有上方。同理对于第一列的任何格子(i, 0)只能从它的上方(i-1, 0)过来。因此初始化dp[0][0]如果起点就是障碍物那直接返回0。否则dp[0][0] 1表示在起点有1种方式不动。初始化第一行for j in range(1, n):如果(0, j)不是障碍物那么dp[0][j] dp[0][j-1]。注意这里不是直接等于1因为如果第一行中某个格子(0, k)是障碍物那么它右边的所有格子(0, j) (jk)都不可能到达路径数应该是0。这个“阻断效应”必须通过递推来体现即dp[0][j]的值依赖于dp[0][j-1]。初始化第一列逻辑同上for i in range(1, m):如果(i, 0)不是障碍物则dp[i][0] dp[i-1][0]。避坑提示绝对不要想当然地把第一行和第一列全部初始化为1。这是无障碍版本“不同路径 I”的做法。在“II”中障碍物会像一堵墙一样挡住整行或整列后续的格子。你必须用递推的方式初始化让障碍物的“阻断”效果传递下去。遍历顺序由于计算dp[i][j]需要dp[i-1][j]上方和dp[i][j-1]左方这两个值必须在dp[i][j]之前被计算出来。最自然的遍历顺序就是两层循环外层i从0到m-1内层j从0到n-1。这样当计算到(i, j)时(i-1, j)上一行同列已经在外层i-1的循环中算过了(i, j-1)本行前一列已经在本层i循环的内层j-1步算过了。这个顺序保证了状态转移的依赖性得到满足。3. 从二维到一维滚动数组的空间优化艺术二维DP的思路清晰代码也容易写。但它的空间复杂度是O(m*n)。在蓝桥杯比赛中虽然通常不会卡空间但掌握空间优化技巧是体现算法功力的重要方面有时也能为其他计算腾出内存。对于这类“每一行的状态只依赖于上一行和本行左侧状态”的DP经典的优化手段就是使用滚动数组将空间复杂度降至O(n)。3.1 滚动数组的工作原理我们仔细观察状态转移方程dp[i][j] dp[i-1][j] dp[i][j-1]。dp[i-1][j]这是“上一行”的j列的值。dp[i][j-1]这是“本行”已经计算出来的j-1列的值。如果我们只用一个一维数组dp_1d来表示“当前行”正在计算的状态那么在计算新的dp_1d[j]即二维中的dp[i][j]时dp_1d[j]本身在上一轮循环计算i-1行时存储的值恰好就是dp[i-1][j]。而dp_1d[j-1]在本次循环中刚刚被更新过它存储的就是dp[i][j-1]。因此状态转移可以在一维数组上原地进行dp_1d[j] dp_1d[j] dp_1d[j-1]等号右边的dp_1d[j]是“旧值”代表从上方来的路径数等号右边的dp_1d[j-1]是“新值”代表从左方来的路径数。等号左边的dp_1d[j]是更新后的当前格子的路径数。3.2 一维DP的初始化与遍历细节使用一维数组后初始化和遍历需要一些调整初始化dp_1d数组现在代表“当前行”。我们初始化它相当于初始化二维DP的第一行。首先dp_1d[0]代表起点(0,0)。如果起点无障碍则dp_1d[0] 1否则为0。对于j从1到n-1如果(0, j)无障碍则dp_1d[j] dp_1d[j-1]因为只能从左来如果有障碍则dp_1d[j] 0。这和二维初始化第一行的逻辑完全一致。遍历外层循环i从1到m-1因为第0行已经初始化好了代表处理第1行到最后一行。在每一行i开始计算前dp_1d数组中存储的实际上是“上一行”i-1行的结果。内层循环j从0到n-1。当j0时第一列计算dp_1d[0]即dp[i][0]。它只能从上方来也就是上一行的dp_1d[0]即dp[i-1][0]。所以如果当前格子(i,0)无障碍新的dp_1d[0]就等于它自身上一行的值如果有障碍则置0。注意此时dp_1d[0]被更新为当前行的值。当j0时执行我们推导出的转移方程dp_1d[j] dp_1d[j] dp_1d[j-1]。但这里有一个极其重要的前提必须保证等号右边的dp_1d[j]和dp_1d[j-1]是正确的值。dp_1d[j-1]在本轮循环中刚刚更新过是对的。dp_1d[j]还是上一行的值也是对的。所以这个计算是安全的。关键点内层循环j必须从0到n-1顺序遍历。因为计算dp_1d[j]依赖于dp_1d[j-1]本行左侧如果从后往前遍历dp_1d[j-1]还是上一行的值逻辑就错了。实操心得在写一维DP代码时我习惯在每一行i的开头先判断当前行的第一个格子第一列。单独处理j0的情况可以让逻辑更清晰避免在j的循环内部做if j0的判断影响代码简洁性和轻微的性能。对于障碍物的判断只需要在更新dp_1d[j]之前检查obstacleGrid[i][j]是否为1即可。4. 代码实现与逐行解析下面给出Python语言的一维滚动数组实现并附上详细注释。这个版本清晰且高效是比赛中的推荐写法。def uniquePathsWithObstacles(obstacleGrid): :type obstacleGrid: List[List[int]] :rtype: int m, n len(obstacleGrid), len(obstacleGrid[0]) # 边界情况1起点就是障碍物 if obstacleGrid[0][0] 1: return 0 # 初始化一维dp数组长度为n列数 dp [0] * n # 初始化起点 dp[0] 1 # 初始化第一行 (i0) for j in range(1, n): # 如果第一行的第j列是障碍物则dp[j]为0且会阻断后续但由于是递推后续自然为0 # 如果不是障碍物则路径数等于左边格子的路径数 dp[j] dp[j-1] if obstacleGrid[0][j] 0 else 0 # 遍历剩余行 (i从1到m-1) for i in range(1, m): # 处理当前行第一列 (j0) # 如果当前格子是障碍物则到此的路径数为0 if obstacleGrid[i][0] 1: dp[0] 0 # 如果不是障碍物dp[0]保持不变因为只能从上方来而dp[0]当前存储的就是上方的值 # 注意这里不需要 dp[0] dp[0]因为值没变。 # 处理当前行剩余列 (j从1到n-1) for j in range(1, n): if obstacleGrid[i][j] 1: # 当前格子是障碍物路径数清零 dp[j] 0 else: # 状态转移dp[j]新 dp[j]旧上方来 dp[j-1]左方来 dp[j] dp[j] dp[j-1] # 最终结果存储在dp数组的最后一个位置 return dp[-1]代码关键点解析dp数组的含义在整个过程中dp[j]表示“在当前正在处理的行i上到达第j列格子的路径总数”。在进入第i行时它存储的是第i-1行的结果在处理完第i行后它存储的是第i行的结果。第一行初始化的循环for j in range(1, n): dp[j] dp[j-1] if obstacleGrid[0][j] 0 else 0。这行代码精妙地处理了第一行的“阻断效应”。如果(0,1)是障碍dp[1]被设为0那么当j2时dp[2] dp[1]自然也是0障碍物右侧全部被正确置零。每行开头对第一列的处理if obstacleGrid[i][0] 1: dp[0] 0。这是必须的因为第一列只能从上方来。如果当前行的第一列是障碍那么到此的路径数就是0并且会“阻断”下方所有行的第一列因为下方格子依赖的上方路径数变成了0。如果不是障碍dp[0]就保持原样因为它本身就代表从上方来的路径数。内层核心转移dp[j] dp[j] dp[j-1]。这是滚动数组优化的精髓。在计算这一刻等号右边的dp[j]是“上一行i-1的第j列的值”等号右边的dp[j-1]是“本行i的第j-1列的值刚刚计算完”。两者相加完美对应了二维的dp[i-1][j] dp[i][j-1]。5. 蓝桥杯国赛实战技巧与常见坑点在国赛的紧张环境中仅仅会解这道题是不够的还要快、要准。下面结合我的备赛和带队经验分享几个针对性的技巧和常见错误。5.1 快速识别与题型变种“不同路径 II”是一个母题蓝桥杯会围绕它做很多变化。看到以下特征要能立刻联想到此类DP网格地图题目给一个m x n的矩阵有可走区域和不可走区域障碍。移动限制通常只能向右、向下有时会增加向左、向上变成搜索或BFS/DFS但DP常见的是单向移动。求解目标求从左上到右下的“路径数”、“最大/最小权重和”、“是否存在路径”等。路径数就是本题状态值表示方案数。最大/最小和每个格子有分数或代价求一条路径使得总分最大或总代价最小。状态转移方程变为dp[i][j] max/min(dp[i-1][j], dp[i][j-1]) grid[i][j]。初始化也要相应调整第一行/列是累加。存在性判断问是否能到达可以用布尔型DP数组或者用本DP方法最后看dp[m-1][n-1]是否大于0。实战技巧在阅读题目时迅速在草稿纸上画出2x3或3x2的小网格手动模拟一下规则。这个小习惯能极大帮助你理解状态转移避免想当然。5.2 初始化与边界处理的致命细节这是错误的重灾区除了前面提到的“第一行第一列递推初始化”外还有几个高频坑点障碍物在起点或终点这是许多同学忘记判定的特例。代码中必须在一开始就检查obstacleGrid[0][0] 1和obstacleGrid[m-1][n-1] 1。如果终点是障碍物直接返回0。虽然从逻辑上讲路径数肯定是0但如果不判断你的DP过程可能会因为某些初始化方式而得到一个非0的错误结果。输入网格为1x1当m1且n1时你的循环可能不会执行。必须单独处理如果这个唯一格子无障碍返回1有障碍返回0。使用一维DP时每行开始对dp[0]的处理务必根据当前行第一列是否有障碍物来重置dp[0]。不能因为它之前有值就不管了。如果当前行(i,0)是障碍dp[0]必须被设为0以阻断后续所有行对第一列的依赖。5.3 调试与验证方法在比赛中写完后快速验证比追求一次写对更重要。设计微型测试用例不要只用题目给的例子。自己设计几个有代表性的小案例案例1[[0]]预期1。案例2[[1]]预期0。案例3[[0,0,0],[0,1,0],[0,0,0]]标准示例预期2。案例4[[0,1],[0,0]]预期1。案例5障碍物完全堵住第一行中间[[0,0,1,0,0]]预期0因为无法绕过障碍到达终点。 用这些案例快速跑一遍你的代码基本能覆盖大部分边界错误。打印DP表如果时间允许或者遇到复杂变种在本地调试时可以打印出二维DP表即使你写的是一维也可以临时用二维来打印中间状态。肉眼对比每个格子的值是否正确是定位初始化或转移方程错误最直接的方法。5.4 空间优化选择的考量在蓝桥杯比赛中对于m和n在100-200量级的题目使用O(m*n)的二维DP空间约40KB-160KB是完全可接受的代码也更易读、易调试。不必为了优化而优化。一维滚动数组的代码相对容易出错尤其是初始化部分。我的建议是在时间紧迫的赛场如果你对二维DP非常有把握可以先写出二维的版本确保正确拿到基础分。如果后面有时间复查并且题目有明确的空间限制提示再考虑优化为一维。清晰的逻辑和正确的答案永远比炫技更重要。在平时练习时则要两种方法都熟练掌握理解其本质。6. 举一反三相关真题与扩展思考掌握了“不同路径 II”你就拥有了解决一大类二维网格DP问题的钥匙。我们可以看看它如何延伸到其他真题。扩展1最小路径和LeetCode 64蓝桥杯常见变种题目给定一个包含非负整数的m x n网格找出一条从左上角到右下角的路径使得路径上的数字总和为最小。解法迁移状态dp[i][j]表示到达(i,j)的最小路径和。转移方程dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]。初始化dp[0][0] grid[0][0]第一行dp[0][j] dp[0][j-1] grid[0][j]第一列dp[i][0] dp[i-1][0] grid[i][0]。同样可以使用滚动数组优化。这和“不同路径 II”的框架完全一致只是把“加法”换成了“取min后加法”。扩展2带权值的不同路径蓝桥杯模拟题题目网格中有障碍每个可通行格子有一个权值正数求所有可达路径的权值之和每条路径的权值是经过格子权值的乘积/和。解法迁移如果是求和那么状态dp[i][j]表示到达(i,j)的所有路径的权值总和。转移方程dp[i][j] dp[i-1][j] dp[i][j-1] count*weight不这里容易搞混。实际上如果路径权值是格子权值之和那么这变成了“路径数”和“最小路径和”的结合体需要更复杂的状态设计。这提示我们DP的状态定义必须与问题要求的结果严格对应。当问题变得复杂时可能需要增加DP的维度。思维进阶如何思考更复杂的网格DP当移动方向增加如可以上下左右或者问题要求更多如路径不能重复、有次数限制单纯的二维坐标DP可能不够用。这时常见的思路是增加状态维度例如用dp[i][j][k]表示在(i,j)且已经使用了k次某种能力的方案数。结合其他算法例如将网格转化为图使用BFS求最短路径无权或Dijkstra算法有权。记忆化搜索当移动规则复杂难以确定递推顺序时用DFS记忆化Memoization可能更直观。这本质上是递归形式的DP思维负担更小但可能有栈溢出风险。回到我们的主题对于冲刺蓝桥杯国赛把“不同路径 II”及其一维优化吃透足以应对大部分基础到中等的二维线性DP题目。核心是训练出看到问题就能抽象出状态定义和转移方程的条件反射同时把初始化、边界处理的细节变成肌肉记忆。在最后的备考阶段多找此类题目进行限时训练总结错题本比盲目刷题更有效。