GESP 七级 · GESP 202606 C++ 七级 第 15 题

在如下网格中，# 表示不能经过的格子，. 表示可以经过的格子。从左上角走到右下角，每次只能向右或向下移动，不同路径共有（ ）条。

. . . . .
. # . # .
. . . . .
# . # . .
. . . . .

仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】动态规划｜障碍网格路径计数

看到“网格 + 障碍”先想 DP，dp[i][j] = (i>0?dp[i-1][j]:0) + (j>0?dp[i][j-1]:0)，若 grid[i][j]==# 则 dp[i][j]=0。dp[0][0]=1，第一行和第一列只要无障碍都是 1。因为每个格子只能从上方或左方到达，所以 dp[i][j] 就是这两个方向路径数之和。逐行计算，遇到障碍直接置 0，最终 dp[4][4] 即为答案。

忽略障碍导致多算。网格中 (1,1) 和 (3,1) 是障碍，DP 时遇到 # 直接置 0。若不看障碍，5×5 无障碍网格从起点到终点需走 8 步（4 右 4 下），组合数 C(8,4)=70，但题目要求“只能向右或向下”且起点终点固定，实际是组合数 C(8,4)=70，障碍会阻断部分路径。正确 DP 得 8 条。

命题人想考我什么？把障碍去掉会变成 C(8,4)=70，把移动方向改成任意会变成图论最短路。把障碍移到 (2,2)，答案会变成多少？刷到此类题先问：“如果去掉障碍/改变方向，答案会怎样？”