AT_dp_y Grid 2 题解

· · 题解

首先我们来考虑题目的弱化版。

若地图中没有障碍，

则从 (1,1) 走到 (H,W) 需要 H+W-2 步，

其中往右的步数为 H-1，

于是答案即为：

C_{H-1}^{H+W-2}

当存在 1 个障碍 (r,c) 时，

考虑用总方案数减去会到达障碍的方案数，

于是答案即为：

C_{H-1}^{H+W-2}- C_{r-1}^{r+c-2} \times C_{H-r}^{H-r+W-c}

当存在 N 个障碍 (r_{i},c_i) 时，

我们令 dp_i 表示从 (1,1) 走到第 i 个障碍且中间无障碍时的路径方案数，

若令 (H,W) 为第 N+1 个障碍，则此时答案为 dp_{N+1}，

于是易得转移方程：

dp_i=C_{r_i-1}^{r_i+c_i-2}-\sum_{j=1}^{i-1} dp_j \times C_{r_i-r_j}^{r_i-r_j+c_i-c_j}

（其中 r_i \ge r_j 且 c_i \ge c_j）

这个转移方程的意思就是将从 (1,1) 到 (r_i,c_i) 的总方案数

减去经过它前面任意其他障碍而到达它的路径。

注意：

实现是简单的。时间复杂度 O(N^2)。