不同路径 II

和无障碍版唯一的差别：遇到障碍格，这一格直接填 0，不再相加。记住这一点，下面每格都在套它。

起点 (0,0)：原地不动也算一种走法，dp[0][0] = 1。

(0,1) 在边上，只有一条来路（左方 dp[0][0]=1），照搬过来 dp[0][1] = 1。

(0,2) 在边上，只有一条来路（左方 dp[0][1]=1），照搬过来 dp[0][2] = 1。

(0,3) 是障碍格（█），机器人根本踏不进来，路径数记 0——它不给下游贡献任何走法。

(0,4) 在边上，唯一来路（左方 dp[0][3]=0）已经是 0——前面被障碍掐断了，所以这里也走不到，dp=0。

(0,5) 在边上，唯一来路（左方 dp[0][4]=0）已经是 0——前面被障碍掐断了，所以这里也走不到，dp=0。

(1,0) 在边上，只有一条来路（上方 dp[0][0]=1），照搬过来 dp[1][0] = 1。

(1,1) 是障碍格（█），机器人根本踏不进来，路径数记 0——它不给下游贡献任何走法。

算 (1,2)：正上方 dp[0][2]=1（蓝），正左方 dp[1][1]=0（蓝），两条来路汇到这里。

相加：1 + 0 = 1，填进 (1,2)。有一条来路是 0（被障碍堵了），只剩另一条贡献。

算 (1,3)：正上方 dp[0][3]=0（蓝），正左方 dp[1][2]=1（蓝），两条来路汇到这里。

相加：0 + 1 = 1，填进 (1,3)。有一条来路是 0（被障碍堵了），只剩另一条贡献。

算 (1,4)：正上方 dp[0][4]=0（蓝），正左方 dp[1][3]=1（蓝），两条来路汇到这里。

相加：0 + 1 = 1，填进 (1,4)。有一条来路是 0（被障碍堵了），只剩另一条贡献。

算 (1,5)：正上方 dp[0][5]=0（蓝），正左方 dp[1][4]=1（蓝），两条来路汇到这里。

相加：0 + 1 = 1，填进 (1,5)。有一条来路是 0（被障碍堵了），只剩另一条贡献。

(2,0) 在边上，只有一条来路（上方 dp[1][0]=1），照搬过来 dp[2][0] = 1。

算 (2,1)：正上方 dp[1][1]=0（蓝），正左方 dp[2][0]=1（蓝），两条来路汇到这里。

相加：0 + 1 = 1，填进 (2,1)。有一条来路是 0（被障碍堵了），只剩另一条贡献。

算 (2,2)：正上方 dp[1][2]=1（蓝），正左方 dp[2][1]=1（蓝），两条来路汇到这里。

相加：1 + 1 = 2，填进 (2,2)。从上面来的、从左边来的，合起来就这么多。

(2,3) 是障碍格（█），机器人根本踏不进来，路径数记 0——它不给下游贡献任何走法。

算 (2,4)：正上方 dp[1][4]=1（蓝），正左方 dp[2][3]=0（蓝），两条来路汇到这里。

相加：1 + 0 = 1，填进 (2,4)。有一条来路是 0（被障碍堵了），只剩另一条贡献。

算 (2,5)：正上方 dp[1][5]=1（蓝），正左方 dp[2][4]=1（蓝），两条来路汇到这里。

相加：1 + 1 = 2，填进 (2,5)。从上面来的、从左边来的，合起来就这么多。

(3,0) 在边上，只有一条来路（上方 dp[2][0]=1），照搬过来 dp[3][0] = 1。

算 (3,1)：正上方 dp[2][1]=1（蓝），正左方 dp[3][0]=1（蓝），两条来路汇到这里。

相加：1 + 1 = 2，填进 (3,1)。从上面来的、从左边来的，合起来就这么多。

算 (3,2)：正上方 dp[2][2]=2（蓝），正左方 dp[3][1]=2（蓝），两条来路汇到这里。

相加：2 + 2 = 4，填进 (3,2)。从上面来的、从左边来的，合起来就这么多。

算 (3,3)：正上方 dp[2][3]=0（蓝），正左方 dp[3][2]=4（蓝），两条来路汇到这里。

相加：0 + 4 = 4，填进 (3,3)。有一条来路是 0（被障碍堵了），只剩另一条贡献。

算 (3,4)：正上方 dp[2][4]=1（蓝），正左方 dp[3][3]=4（蓝），两条来路汇到这里。

相加：1 + 4 = 5，填进 (3,4)。从上面来的、从左边来的，合起来就这么多。

算 (3,5)：正上方 dp[2][5]=2（蓝），正左方 dp[3][4]=5（蓝），两条来路汇到这里。

相加：2 + 5 = 7，填进 (3,5)。从上面来的、从左边来的，合起来就这么多。

表填满了。右下角 dp[3][5] = 7，就是绕开 3 个障碍、从左上走到右下的不同路径总数。

极端输入先想清楚：起点/终点是障碍都要能正确返回 0。

两个高频追问。