algorithm - 在具有特定限制的情况下查找网格中的路径数

Question

给定一个 n 行 m 列的矩形网格。行从下到上编号为 1 到 n，列从左到右编号为 1 到 m。

你还得到了 k 个特殊字段，形式为 (row, column)。对于每个 i，其中 0 <= i <= k，计算从 (1, 1) 到 (n, m) 恰好包含 n 个特殊字段的不同路径的数量。

您必须遵守一条规则。您只能进行笔直向上或向右的移动。也就是说，从每个字段(行，列)，只能移动到字段(行+1，列)或者字段(行，列+1)。

输出一个包含 k + 1 个元素的数组。第 i 个元素(从 0 开始)必须是恰好包含 i 个特殊字段的不同路径的数量。因为，答案可能太大，输出它模 1000007。

输入: 第一行包含三个空格分隔的整数，n、m 和 k。接下来的k行，每行包含两个空格分隔的整数，一个特殊字段的坐标。

输出: k + 1 个空格分隔的整数，问题的答案。

约束: 1 <= n, m, k <= 100 对于所有坐标 (r, c) - 1 <= r <= n, 1 <= c <= m 所有坐标均有效且不同。

Answer 1

这是一个简单的 DP:

初始化:

T[i][0][k] = 0
T[0][j][k] = 0

如果 grid[1][1] 不特殊:

T[1][1][k!=0] = 0
T[1][1][0] = 1

否则:

T[1][1][k!=1] = 0
T[1][1][1] = 1

批量:

如果 grid[i][j] 不特殊:

T[i][j][k] = (T[i-1][j][k] + T[i][j-1][k]) % 1000007

否则:

T[i][j][0] = 0
T[i][j][k>0] = (T[i-1][j][k-1] + T[i][j-1][k-1]) % 1000007

回答:

T[n][m][k], for every possible k.