P3398. 园区参观路径

解题思路

题目背景

注意，本题与 不同路径 II 完全一致，属于经典的 二维 DP 路径问题。

核心思路

使用 动态规划 解决。定义 dp[i][j] 表示从起点到达网格中第 i 行第 j 列位置的不同路径数。

状态转移

如果当前位置 (i, j) 不是障碍物，则路径数等于上方和左方路径数之和：

如果当前位置是障碍物，则路径数为 0：

初始化

• 起点 (0, 0) 如果无障碍物，则 dp[0][0] = 1，否则为 0。
• 第一行和第一列：若无障碍物，则路径数继承前一个位置的值；若有障碍物，则后续位置均为 0。

关键结论

• 本题与 不同路径 II 解法完全一致，只需处理障碍物判断。
• 时间复杂度 O(m × n)，空间复杂度可优化为 O(n)。

思路展开 先把题目翻译成网格模型：园区是一个 n 行 m 列的网格，输入中每个格子的值为 0 或 1，1 表示该位置不能通行（代码中 grid[i][j] == 1 的分支处理的就是它），起点在左上角 (0,0)，终点在右下角 (n-1,m-1)，每一步只能向右或向下。 dp[i][j] 表示从起点走到第 i 行第 j 列一共有多少条不同路径。因为只能向右或向下走，到达 (i,j) 的最后一步要么来自左边的 (i,j-1)，要么来自上边的 (i-1,j)，这两类路径互不重叠，所以 dp[i][j] = dp[i][j-1] + dp[i-1][j]；若 (i,j) 本身不可通行，代码用 continue 跳过，它的路径数保持为 0，后续格子自然不会从这里获得任何方案数。 初始化时，第一行和第一列各自只有一条一路向右或一路向下的走法，所以逐格记为 1；而一旦在第一行或第一列上遇到障碍，它后面的格子就再也无法沿边界到达，代码用 break 提前停止，这些格子保持默认值 0。 双重循环按行从上到下、按列从左到右推进，保证计算 dp[i][j] 时它依赖的左、上两个值都已经算好。最后输出 dp[n-1][m-1]，即到达右下角的路径总数。