给一个h×m的网格，一开始在左上角 （1,1） 每一步只能向右或向下走，不能经过 '#' 格子，求走到右下角（h，m）有多少种走法。

这是一个经典的动态规划问题。定义一个二维数组 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 代码实现：

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++语言进行编程

可以使用动态规划算法来解决这个问题，具体实现如下：

#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$，其中 $dp[i][j]$ 表示从 $(0,0)$ 出发到达 $(i,j)$ 的不同路径数目。

根据题目要求，机器人只能向下或向右走，因此对于任意一个格子 $(i,j)$，它只能从上方格子 $(i-1,j)$ 或左方格子 $(i,j-1)$ 走过来，因此有：

$$dp[i][j] = dp[i-1][j] + dp[i][j-1]$$

初始条件为 $dp[0][0]=1$，即起点只有一种到达方式。

最终答案为 $dp[m-1][n-1]$，即从起点到终点的不同路径数目。

以下是Python代码实现：

def uniquePaths(m: int, n: int) -> int:
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1
    for i in range(m):
        for j in range(n):
            if i > 0:
                dp[i][j] += dp[i-1][j]
            if j > 0:
                dp[i][j] += dp[i][j-1]
    return dp[m-1][n-1]

时间复杂度为 $O(mn)$，空间复杂度为 $O(mn)$。