不同路径 II

最直接的想法是从起点递归，每格往右、往下各试一次，数到终点的路径条数。可同一个格子会被无数条前缀重复访问，「从这格到终点有几条路」被反复重算，网格一大就指数爆炸。

转折：用 dp[i][j] 记「走到这格有几条路」，每格只算一次。一个格子只能从上面或左边来，所以 dp[i][j] = dp[i−1][j] + dp[i][j−1]。遇到障碍，谁也站不上去，dp 直接置 0——它就不会再把路径数传给右边和下边，那些经过障碍的路自动被掐断。

建表 · 起点 dp[0][0]=1：建一张 3×3 的 dp 表，行列数全程不变。起点不是障碍，站在那儿本身就算 1 条路，先填 dp[0][0]=1。其余先空着，按从上到下、从左到右逐格填。

第一行 · 只能向右：第一行头顶没有格子，只能一路向右走过来。这一行没障碍，所以全是 1，就是一条直路。

第一列 · 只能向下：第一列同理，只能一路向下，也没障碍，也全是 1。现在边界铺好了，开始填中间。

障碍格 (1,1) = 0：轮到正中央，它是障碍。这里走障碍分支：不算上+左，直接把 dp 记成 0——没有任何走法能合法停在障碍上。这个 0 待会儿会传给它右边和下边。

填 (1,2) · 上1 + 左0：这格不是障碍，正常算上+左：上面是 1，左边是障碍传来的 0，相加只剩 1 条路。障碍的 0 在这里第一次起作用，把原本能从左边来的路抹掉了。

填 (2,1) · 上0 + 左1：这格也算上+左：上面又是障碍传来的 0，左边是 1，结果 1 条路。可以看到障碍的 0 同时切断了右边和下边两个方向。

右下角 · 上1 + 左1：终点 = 上面 1 + 左边 1 = 2。这正是绕过中央障碍的那 2 条路：贴上边绕一条、贴下边绕一条。

答案：右下角 dp[2][2] = 2 就是答案。整张表填完，障碍那格的 0 把所有穿过它的路都拦住了。

网格 DP 里碰到不可用的格子，把它的 dp 置 0（计数题）或置无穷（最值题），它就不会再把值传给右边、下边——障碍、陷阱、禁区都这么处理。

雷区实演 · 起点就是障碍：把起点换成障碍试一下：dp[0][0] 一开始就该是 0，不能写 1。0 一路向右、向下传，整张表全是 0，最后答案是 0。这就是为什么必须先特判起点。

几个高频追问，记住答法。

迁移阶梯：把这题练到能复述后，去网格 DP 专题里迁移：状态定义照搬，只改边界和「障碍清零」这一笔。卡住就问问 AI 助教，或进通关训练实战一遍。

边界三连：边界三连：起点障碍、终点障碍、单格网格，极端输入先各过一遍。