企业官网建设流程全解析

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来表示。这意味着，机器人不能进入有障碍物的格子，任何一条路径也不能包含障碍物。

这个看似简单的改动，却引入了几个必须仔细处理的难点：

1. 起点或终点即障碍：如果起点(0,0)或终点(m-1, n-1)本身就是障碍物，那么显然路径数为0。这是一个需要最先判断的边界情况。
2. 状态转移方程的中断：在经典问题中，到达(i, j)的路径数等于从上方(i-1, j)和左方(i, j-1)来的路径数之和。但现在，如果(i, j)本身是障碍物，那么dp[i][j]应该直接为0，因为它是一个不可达的点。更重要的是，如果(i-1, j)或(i, j-1)是障碍物，那么从那个方向来的路径数就是0，而不是参与求和。
3. 初始化第一行和第一列的复杂性：在经典问题中，第一行和第一列的格子都只有一种走法（一直向右或一直向下）。但现在，如果第一行中某个格子(0, j)是障碍物，那么它右边的所有格子(0, k) (k>j)都将是不可达的，因为机器人无法越过这个障碍。第一列同理。

这些难点归结到一点：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。

初始化是重中之重，也是最容易出错的地方：

1. 起点：dp[0][0]的值完全取决于obstacleGrid[0][0]。如果是障碍，直接返回0；否则，dp[0][0] = 1，因为起点就是一条路径（不动）。
2. 第一行 (i=0)：对于j从1到n-1，dp[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

3. 第一列 (j=0)：逻辑与第一行对称。对于i从1到m-1：

   if 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：

1. 如果obstacleGrid[i][j] == 1（当前是障碍），则dp[i][j] = 0。
2. 否则，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行时，我们只需要：

1. 一个数组prev_row，保存着第i-1行的dp值（即上一行的结果）。
2. 一个数组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列的值。

1. 第一行 (i=0)的初始化：
   • 首先处理起点：dp[0] = 1 if obstacleGrid[0][0] == 0 else 0。
   • 然后对于j从1到n-1：dp[j] = dp[j-1] if obstacleGrid[0][j] == 0 else 0。这里dp[j-1]已经是本行（第0行）前一个格子的值。如果遇到障碍，dp[j]及之后的所有dp值（在本行内）本应都为0，但我们的循环逻辑会自然处理这一点：一旦dp[j]被设为0，那么dp[j+1] = dp[j] + ...也将会是0。
2. 后续行 (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 滚动数组的陷阱与调试心得

从我个人的踩坑经验来看，使用滚动数组时最容易在两个地方出错：

1. 第一列的更新逻辑：很多人会忘记在每一行开始时单独处理dp[0]。错误地认为dp[0]在整个过程中都只由第一行决定。实际上，对于i>0的行，dp[0]代表从起点(0,0)走到(i,0)的路径数。如果(i,0)不是障碍，那么dp[0]应该等于上一行的dp[0]（因为只能从上方来）；如果是障碍，则必须置0。这个更新必须在j循环之前完成。
2. 状态转移的语义混淆：在dp[j] = dp[j] + dp[j-1]这行代码里，等号右边的两个dp含义不同，这是理解滚动数组的关键。我建议在代码注释中明确写出# dp[j] (old)来自上方， dp[j-1] (new)来自左方。调试时，可以打印出每一行计算后的dp数组，观察其变化是否符合预期。

滚动数组的掌握，是DP能力进阶的标志。它不仅仅是为了省内存，更是一种对状态转移依赖关系的深刻理解。在蓝桥杯等竞赛中，对空间复杂度有明确要求的题目并不少见，掌握这个技巧能让你在解题时更加游刃有余。

5. 测试用例设计与边界情况全覆盖

再好的算法，也需要经过严密测试。对于“不同路径 II”，我们必须设计覆盖所有特殊情况的测试用例。以下是我总结的必备测试集：

在编写完代码后，务必用这些用例逐一测试。特别是“障碍封住第一行/第一列”的用例，能有效检验你的初始化代码是否将障碍后的格子正确置零。

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] * (W+1) 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”这道题，完美串联了多个考点：

1. 动态规划基础建模：如何将问题转化为重叠子问题和最优子结构。
2. 边界条件处理：竞赛题目的陷阱往往就在边界。起点终点障碍、第一行第一列被阻断，都是考官爱设的“坑”。
3. 空间优化：滚动数组是国赛级别题目中常见的优化要求。它考察你是否真正理解了状态转移的过程，而不是死记模板。
4. 代码实现严谨性：初始化顺序、循环边界、条件判断，每一处都需要仔细推敲。

在刷题时，我建议遵循这样的步骤：

1. 先写出二维DP的“标准解”。确保逻辑完全正确，通过所有测试用例。这是保底分，也是理解问题的根本。
2. 在标准解的基础上，推导滚动数组优化。像我们上面做的那样，分析依赖关系，重写转移方程和初始化。务必在代码中加上清晰的注释，说明dp[j]在等号两边分别代表什么。
3. 对比测试。用同一组测试用例验证优化前后的代码，确保结果一致。

这道题掌握后，可以顺势去攻克LeetCode上其他的DP题目，比如“最小路径和”、“地下城游戏”等，它们的状态转移和初始化各有特点，但核心的DP思想和空间优化技巧是相通的。动态规划是蓝桥杯的重中之重，把基础打牢，把一道题吃透，远胜过盲目刷一百道题。