给一个h×m的网格,一开始在左上角 (1,1) 每一步只能向右或向下走,不能经过 '#' 格子,求走到右下角(h,m)有多少种走法。
时间: 2024-02-24 16:57:11 浏览: 35
这是一个经典的动态规划问题。定义一个二维数组 dp,其中 dp[i][j] 表示从起点 (1,1) 走到网格中第 i 行第 j 列的位置的不同路径数。则有状态转移方程:
dp[i][j] = 0, 如果 (i,j) 位置为 '#';
dp[i][j] = dp[i-1][j] + dp[i][j-1], 如果 (i,j) 位置不为 '#'。
边界条件为 dp[1][1] = 1,dp[1][j] = dp[i][1] = 1(第一行和第一列只有一种走法,因为只能向右或向下走)。
最终的答案为 dp[h][m]。时间复杂度为 O(hm)。
以下是 Python 代码实现:
```python
def countPaths(grid):
h, m = len(grid), len(grid[0])
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×m 的二维网格,用 '#' 表示障碍格子,用其他字符表示可通行格子。
相关问题
给一个H×W的网格,一开始在左上角(1,1)每一步只能向右或向下走,不能经过 '#' 格子,求走到右下角(H,W)有多少种走法。 用C++语言进行编程
可以使用动态规划算法来解决这个问题,具体实现如下:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int N = 105;
char g[N][N];
int f[N][N];
int main() {
int h, w;
cin >> h >> w;
// 输入网格图
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
cin >> g[i][j];
}
}
// 初始化边界条件
f[1][1] = 1;
for (int i = 2; i <= w; i++) {
if (g[1][i] != '#') {
f[1][i] = f[1][i - 1];
}
}
for (int i = 2; i <= h; i++) {
if (g[i][1] != '#') {
f[i][1] = f[i - 1][1];
}
}
// 计算状态转移方程
for (int i = 2; i <= h; i++) {
for (int j = 2; j <= w; j++) {
if (g[i][j] != '#') {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
}
// 输出结果
cout << f[h][w] << endl;
return 0;
}
```
时间复杂度为 O(HW),空间复杂度为 O(HW)。
给定m行和n列网格,有一个机器人从左上角(0,0)出发,每一步可以向下或向右走一步,问多少种不同的方式走到右下角?
这是一个典型的动态规划问题。我们可以用 $dp_{i,j}$ 表示从左上角走到第 $i$ 行,第 $j$ 列的格子的不同路径数。显然,$dp_{0,0}=1$,因为只有一种走法,即不动。
对于第一行和第一列的格子,因为机器人只能向右或向下移动,所以每个格子的 $dp$ 值都是 1,即 $dp_{0,j}=dp_{i,0}=1$。
对于其他的格子,它们既可以从上方的格子到达,也可以从左边的格子到达,因此有:
$$dp_{i,j}=dp_{i-1,j}+dp_{i,j-1}$$
最终,$dp_{m-1,n-1}$ 就是从左上角走到右下角的不同路径数。
下面是 Python 代码实现:
```python
def uniquePaths(m: int, n: int) -> int:
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
```
时间复杂度为 $O(mn)$,空间复杂度为 $O(mn)$。