1. 从“不同路径”到“不同路径二”一道题背后的算法思维跃迁如果你正在备战蓝桥杯或者刷LeetCode时卡在了动态规划DP的入门与进阶之间那么“不同路径 II”这道题绝对是一个绝佳的跳板。它不像“斐波那契数列”那样直白也不像“背包问题”那样复杂而是恰到好处地卡在了一个承上启下的位置。很多人刷完基础的“不同路径”觉得DP不过如此无非是dp[i][j] dp[i-1][j] dp[i][j-1]但一遇到“II”里面的障碍物思路瞬间就乱了套代码写出来也又臭又长。这道题的核心价值远不止于算出有多少条路径。它强迫你去思考DP中两个最关键的进阶概念状态转移方程的边界条件处理以及空间复杂度的极致优化——滚动数组。前者决定了你的算法逻辑是否严谨能否处理各种“坑”后者则决定了你的算法在竞赛或面试中是否具备竞争力。我见过太多代码能算出正确答案但用了O(m*n)的二维数组在数据量稍大时便显得笨重。而真正高效的解法往往能将空间压缩到O(n)甚至O(1)。今天我们就来彻底拆解这道题不仅让你AC更要让你理解每一步背后的“为什么”并掌握滚动数组这一利器为冲刺蓝桥杯国赛级别的题目打下坚实基础。2. 问题重述与核心难点分析障碍物如何“阻断”状态转移我们先明确问题。在经典的“不同路径”问题中一个机器人位于一个m x n网格的左上角每次只能向下或者向右移动一步问到达右下角有多少条不同的路径。网格中所有格子都是可通行的。而“不同路径 II”在此基础上增加了一个约束网格中可能存在障碍物。障碍物和空位置分别用1和0来表示。这意味着机器人不能进入有障碍物的格子任何一条路径也不能包含障碍物。这个看似简单的改动却引入了几个必须仔细处理的难点起点或终点即障碍如果起点(0,0)或终点(m-1, n-1)本身就是障碍物那么显然路径数为0。这是一个需要最先判断的边界情况。状态转移方程的中断在经典问题中到达(i, j)的路径数等于从上方(i-1, j)和左方(i, j-1)来的路径数之和。但现在如果(i, j)本身是障碍物那么dp[i][j]应该直接为0因为它是一个不可达的点。更重要的是如果(i-1, j)或(i, j-1)是障碍物那么从那个方向来的路径数就是0而不是参与求和。初始化第一行和第一列的复杂性在经典问题中第一行和第一列的格子都只有一种走法一直向右或一直向下。但现在如果第一行中某个格子(0, j)是障碍物那么它右边的所有格子(0, k) (kj)都将是不可达的因为机器人无法越过这个障碍。第一列同理。这些难点归结到一点DP表格的填充不再是一个无脑的累加过程而是每一步都需要根据当前格子和其来源格子的状态是否为障碍进行条件判断。理解这一点是写出正确代码的前提。3. 基础二维DP解法一步步构建严谨的逻辑框架我们先从最直观的二维DP解法开始这是理解问题本质的最佳途径。我们定义一个二维数组dp[i][j]表示从起点(0,0)走到格子(i,j)的不同路径数量。输入网格记为obstacleGrid。3.1 状态定义与初始化dp[i][j]: 从(0,0)到(i,j)的路径数其中obstacleGrid[i][j] 0。如果obstacleGrid[i][j] 1则dp[i][j] 0。初始化是重中之重也是最容易出错的地方起点dp[0][0]的值完全取决于obstacleGrid[0][0]。如果是障碍直接返回0否则dp[0][0] 1因为起点就是一条路径不动。第一行 (i0)对于j从1到n-1dp[0][j]能否为1取决于两个条件当前格子不是障碍obstacleGrid[0][j] 0它左边的格子是可达的dp[0][j-1] 1只有同时满足dp[0][j]才能继承dp[0][j-1]的路径数即1否则为0。用代码表示就是if obstacleGrid[0][j] 0 and dp[0][j-1] 1: dp[0][j] 1 else: dp[0][j] 0第一列 (j0)逻辑与第一行对称。对于i从1到m-1if obstacleGrid[i][0] 0 and dp[i-1][0] 1: dp[i][0] 1 else: dp[i][0] 0注意这里判断dp[0][j-1] 1而不是obstacleGrid[0][j-1] 0是因为dp值才真正代表了可达性。一个格子不是障碍但如果它左边的格子不可达它依然不可达。3.2 状态转移方程与填充顺序对于其他位置(i, j)其中i 0且j 0如果obstacleGrid[i][j] 1当前是障碍则dp[i][j] 0。否则dp[i][j] dp[i-1][j] dp[i][j-1]。这里有一个隐含的优化我们不需要额外判断dp[i-1][j]和dp[i][j-1]是否为障碍因为如果它们是障碍它们在之前被计算时dp值就已经是0了。所以直接相加即可0值不会对结果产生贡献。填充顺序很简单就是普通的二重循环先遍历行i再遍历列j。因为计算dp[i][j]时它所依赖的dp[i-1][j]上一行和dp[i][j-1]本行前一列都已经被计算出来了。3.3 完整代码示例与复杂度分析def uniquePathsWithObstacles(obstacleGrid): m, n len(obstacleGrid), len(obstacleGrid[0]) # 情况1: 起点或终点是障碍 if obstacleGrid[0][0] 1 or obstacleGrid[m-1][n-1] 1: return 0 dp [[0] * n for _ in range(m)] # 初始化起点 dp[0][0] 1 # 初始化第一行 for j in range(1, n): if obstacleGrid[0][j] 0 and dp[0][j-1] 1: dp[0][j] 1 # else 保持为0 (默认值) # 初始化第一列 for i in range(1, m): if obstacleGrid[i][0] 0 and dp[i-1][0] 1: dp[i][0] 1 # 填充其余部分 for i in range(1, m): for j in range(1, n): if obstacleGrid[i][j] 0: dp[i][j] dp[i-1][j] dp[i][j-1] # else 保持为0 return dp[m-1][n-1]复杂度分析时间复杂度O(m * n)。我们遍历了整个网格一次。空间复杂度O(m * n)。我们使用了一个同等大小的二维dp数组。这个解法逻辑清晰易于理解是标准的DP解法。在蓝桥杯或面试中能清晰无误地写出这个解法已经可以拿到大部分分数。但是如果我们想追求极致尤其是在m或n很大时O(m*n)的空间开销是可以优化的。这就是滚动数组登场的时候。4. 空间优化核心滚动数组的降维打击仔细观察状态转移方程dp[i][j] dp[i-1][j] dp[i][j-1]。你会发现计算第i行的dp值时它只依赖于两个数据上一行同列的dp[i-1][j]以及本行前一列的dp[i][j-1]。这意味着我们并不需要保存整个m行的历史数据。在计算第i行时我们只需要一个数组prev_row保存着第i-1行的dp值即上一行的结果。一个数组curr_row我们正在计算的第i行的dp值。更进一步我们甚至可以用一个一维数组dp来同时扮演这两个角色通过原地更新来实现。这就是滚动数组的思想。4.1 一维滚动数组的推导我们定义一维数组dp[j]。在计算到第i行时dp[j]表示什么在开始计算第i行第j列之前dp[j]里存储的值实际上是上一行第j列的结果即dp[i-1][j]。而dp[j-1]呢因为我们是按j从0到n-1的顺序计算的当计算到dp[j]时dp[j-1]已经被更新为第i行第j-1列的结果了即dp[i][j-1]。看我们需要的两个值dp[i-1][j]和dp[i][j-1]恰好对应着当前dp[j]未更新和dp[j-1]已更新的值。因此状态转移可以改写为新的dp[j] 旧的dp[j] dp[j-1]当然前提是当前格子不是障碍物。如果当前格子(i, j)是障碍物那么无论从哪来路径数都是0所以我们需要将dp[j]显式地设置为0。4.2 初始化与边界处理的重构使用一维数组后初始化逻辑也需要调整。现在dp[j]在每一行迭代开始时代表的是上一行j列的值。第一行 (i0)的初始化首先处理起点dp[0] 1 if obstacleGrid[0][0] 0 else 0。然后对于j从1到n-1dp[j] dp[j-1] if obstacleGrid[0][j] 0 else 0。这里dp[j-1]已经是本行第0行前一个格子的值。如果遇到障碍dp[j]及之后的所有dp值在本行内本应都为0但我们的循环逻辑会自然处理这一点一旦dp[j]被设为0那么dp[j1] dp[j] ...也将会是0。后续行 (i 0)的处理每一行开始计算时dp[0]第一列需要单独处理因为它没有左边的格子(j-1)。它的值取决于当前格子不是障碍并且上一行的dp[0]即从上方来的路径不为0。用代码就是dp[0] dp[0] if obstacleGrid[i][0] 0 else 0。注意这里的dp[0]在等号右边是上一行的结果等号左边是更新为本行的结果。然后对于j从1到n-1应用我们的核心转移逻辑if obstacleGrid[i][j] 1: dp[j] 0 # 当前是障碍不可达 else: dp[j] dp[j] dp[j-1] # dp[j]是旧的(来自上方)dp[j-1]是新的(来自左方)4.3 一维滚动数组完整代码def uniquePathsWithObstacles(obstacleGrid): m, n len(obstacleGrid), len(obstacleGrid[0]) if obstacleGrid[0][0] 1 or obstacleGrid[m-1][n-1] 1: return 0 dp [0] * n # 初始化第一行 dp[0] 1 if obstacleGrid[0][0] 0 else 0 for j in range(1, n): # 如果当前格子可走且左边格子可达则路径数等于左边格子的路径数 # 如果左边格子不可达dp[j-1]0这里也会自然得到0 dp[j] dp[j-1] if obstacleGrid[0][j] 0 else 0 # 处理后续行 for i in range(1, m): # 更新当前行的第一列 dp[0] dp[0] if obstacleGrid[i][0] 0 else 0 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-1]来自左方 return dp[n-1]复杂度分析时间复杂度O(m * n)不变。空间复杂度O(n)。我们只使用了一个长度为n列数的一维数组。在m和n相差悬殊时优化效果显著。4.4 滚动数组的陷阱与调试心得从我个人的踩坑经验来看使用滚动数组时最容易在两个地方出错第一列的更新逻辑很多人会忘记在每一行开始时单独处理dp[0]。错误地认为dp[0]在整个过程中都只由第一行决定。实际上对于i0的行dp[0]代表从起点(0,0)走到(i,0)的路径数。如果(i,0)不是障碍那么dp[0]应该等于上一行的dp[0]因为只能从上方来如果是障碍则必须置0。这个更新必须在j循环之前完成。状态转移的语义混淆在dp[j] dp[j] dp[j-1]这行代码里等号右边的两个dp含义不同这是理解滚动数组的关键。我建议在代码注释中明确写出# dp[j] (old)来自上方 dp[j-1] (new)来自左方。调试时可以打印出每一行计算后的dp数组观察其变化是否符合预期。滚动数组的掌握是DP能力进阶的标志。它不仅仅是为了省内存更是一种对状态转移依赖关系的深刻理解。在蓝桥杯等竞赛中对空间复杂度有明确要求的题目并不少见掌握这个技巧能让你在解题时更加游刃有余。5. 测试用例设计与边界情况全覆盖再好的算法也需要经过严密测试。对于“不同路径 II”我们必须设计覆盖所有特殊情况的测试用例。以下是我总结的必备测试集测试用例描述输入网格 (obstacleGrid)预期输出验证点基础无障碍[[0,0,0],[0,0,0],[0,0,0]](3x3)6验证基础DP公式正确性单障碍在中间[[0,0,0],[0,1,0],[0,0,0]]2验证障碍物能正确阻断路径起点即障碍[[1,0],[0,0]]0验证最直接的边界条件终点即障碍[[0,0],[0,1]]0验证另一个直接边界条件障碍封住第一行[[0,1,0],[0,0,0],[0,0,0]]0验证第一行初始化逻辑障碍封住第一列[[0,0,0],[1,0,0],[0,0,0]]0验证第一列初始化逻辑单行网格[[0,0,0,0,1]]0验证行或列为1时的处理单列网格[[0],[0],[1],[0]]0验证行或列为1时的处理大网格无障碍100x100全0网格结果很大验证无溢出验证算法效率与数值范围Python无此问题C需注意在编写完代码后务必用这些用例逐一测试。特别是“障碍封住第一行/第一列”的用例能有效检验你的初始化代码是否将障碍后的格子正确置零。6. 举一反三滚动数组在其他DP问题中的应用模式掌握了“不同路径 II”中的滚动数组我们来看看这种优化思路如何迁移到其他经典DP问题上。其核心在于识别状态转移的依赖范围。6.1 经典应用0-1背包问题0-1背包问题的经典二维DP定义是dp[i][w]表示考虑前i个物品在背包容量为w时的最大价值。状态转移方程为dp[i][w] max(dp[i-1][w], dp[i-1][w-weight[i]] value[i])观察方程计算第i行时只依赖于第i-1行。并且dp[i][w]依赖于dp[i-1][w]和dp[i-1][w-weight[i]]后者是更小容量的状态。因此如果我们将w容量的循环从大到小遍历就可以用一维数组dp[w]实现滚动优化dp [0] * (W1) for i in range(N): # 遍历物品 for w in range(W, weight[i]-1, -1): # 逆序遍历容量 dp[w] max(dp[w], dp[w - weight[i]] value[i])为什么逆序因为我们需要在计算dp[w]时dp[w - weight[i]]保存的还是上一轮i-1的值。如果正序遍历dp[w - weight[i]]可能已经被本轮i更新过了这就变成了“完全背包”问题的逻辑违反了每个物品只能用一次的原则。6.2 进阶思考其他依赖模式滚动数组的应用前提是状态转移的依赖关系有限。除了依赖“上一行”这种最常见的情况还有依赖左上角例如一些编辑距离类问题。优化时需要更巧妙的处理有时可能需要额外的临时变量。依赖固定窗口例如dp[i]只依赖于dp[i-1],dp[i-2], ...,dp[i-k]。此时可以用一个长度为k的数组或队列来滚动将空间复杂度从O(n)降到O(k)。核心判断方法画出DP表观察计算当前状态dp[i][j]时需要哪些已经计算过的状态。如果这些状态都集中在有限的几行或几列那么滚动数组优化就很有可能。7. 蓝桥杯备赛视角下的总结与延伸回到我们备战蓝桥杯的语境。“不同路径 II”这道题完美串联了多个考点动态规划基础建模如何将问题转化为重叠子问题和最优子结构。边界条件处理竞赛题目的陷阱往往就在边界。起点终点障碍、第一行第一列被阻断都是考官爱设的“坑”。空间优化滚动数组是国赛级别题目中常见的优化要求。它考察你是否真正理解了状态转移的过程而不是死记模板。代码实现严谨性初始化顺序、循环边界、条件判断每一处都需要仔细推敲。在刷题时我建议遵循这样的步骤先写出二维DP的“标准解”。确保逻辑完全正确通过所有测试用例。这是保底分也是理解问题的根本。在标准解的基础上推导滚动数组优化。像我们上面做的那样分析依赖关系重写转移方程和初始化。务必在代码中加上清晰的注释说明dp[j]在等号两边分别代表什么。对比测试。用同一组测试用例验证优化前后的代码确保结果一致。这道题掌握后可以顺势去攻克LeetCode上其他的DP题目比如“最小路径和”、“地下城游戏”等它们的状态转移和初始化各有特点但核心的DP思想和空间优化技巧是相通的。动态规划是蓝桥杯的重中之重把基础打牢把一道题吃透远胜过盲目刷一百道题。