一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“start” )。 机

器人每次只能向下或者向右移动一格，直到到达右下角的终点（下图中标记为“end”）。现在给定了一些障碍物用 1 来表示，机器人不能通过。请问机器人能否到达终点？

这是一道动态规划问题。我们可以定义一个二维数组 dp，其中 dp[i][j] 表示机器人到达(i, j)这个位置是否可行（1 表示可行，0 表示不可行）。那么我们需要先初始化 dp 数组：

- 如果起点 (0, 0) 有障碍物，dp[0][0] = 0;
- 否则，dp[0][0] = 1;
- 对于第一行和第一列，如果前一个格子可行并且当前格子没有障碍物，那么当前格子也可行，即 dp[0][j] = dp[0][j-1] && obstacleGrid[0][j] = 0，dp[i][0] = dp[i-1][0] && obstacleGrid[i][0] = 0;
- 对于其他格子 (i, j)，如果当前格子没有障碍物，那么机器人到达当前格子的路径有两种可能：从上面的格子到达或者从左边的格子到达。即 dp[i][j] = dp[i-1][j] + dp[i][j-1]。

最终，dp[m-1][n-1] 就表示了机器人能否到达终点。如果 dp[m-1][n-1] 为 1，那么可以到达终点；否则不能到达。

相关问题

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？

这是一个经典的组合问题，可以使用组合数学的方法来解决。机器人需要向右移动 n-1 次，向下移动 m-1 次，总共需要移动 n-1+m-1=n+m-2 次。因此，不同的路径数就是从 n+m-2 个元素中选择 n-1 个元素的组合数，即 C(n+m-2, n-1)。

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start”）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。 问总共有多少条不同的路径？使用C++

这是一个经典的动态规划问题，通常被称为“机器人走迷宫”。在C++中，你可以使用二维数组dp来解决这个问题，其中dp[i][j]表示到达位置(i, j)的不同路径数。以下是解决此问题的基本算法步骤：

1. 初始化：dp[0][0] = 1，因为从起点出发到起点只有一条路。

2. 动态转移：对于每个位置(i, j)，如果i > 0，那么上一格dp[i - 1][j]可以到达这个位置，所以dp[i][j] += dp[i - 1][j]；同理，如果j > 0，那么左边dp[i][j - 1]也可以到达，所以dp[i][j] += dp[i][j - 1]。

3. 返回结果：当到达右下角(即i == m - 1 && j == n - 1)时，dp[m - 1][n - 1]就是总的路径数。

下面是一个简单的C++函数实现：

int uniquePaths(int m, int n) {
    if (m <= 0 || n <= 0) return 0;
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = 1;

    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0];
    }
    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1];
    }

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1];
}