给一个h×m的网格,一开始在左上角 (1,1) 每一步只能向右或向下走,不能经过 '#' 格子,求走到右下角(h,m)有多少种走法。
时间: 2024-03-04 08:48:40 浏览: 126
这是一个典型的动态规划问题,可以使用动态规划求解。我们可以用 $dp_{i,j}$ 表示从起点到网格中第 $i$ 行第 $j$ 列的格子的不同走法数目。
初始化时,$dp_{1,j}=1$ 和 $dp_{i,1}=1$,因为只有一行或一列时只有一种走法。
对于其他格子 $(i,j)$,它可能是从上方的格子 $(i-1,j)$ 走下来的,也可能是从左边的格子 $(i,j-1)$ 走过来的,因此有:
$$
dp_{i,j} = \begin{cases}
dp_{i-1,j}+dp_{i,j-1} & \text{if } grid_{i,j}\neq\# \\
0 & \text{otherwise}
\end{cases}
$$
最终答案即为 $dp_{h,m}$。
下面是 Python 代码实现:
```python
def uniquePaths(h: int, m: int, grid: List[List[str]]) -> int:
dp = [[0] * (m+1) for _ in range(h+1)]
dp[1][1] = 1
for i in range(1, h+1):
for j in range(1, m+1):
if grid[i-1][j-1] == '#':
dp[i][j] = 0
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[h][m]
```
其中,`grid` 表示网格,是一个 $h\times m$ 的二维列表。
阅读全文