一个机器人位于一个 m x n 网格的左上角，机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角，问总共有多少条不同的路径？用c++代码实现

这是一个经典的动态规划问题。假设网格的左上角为起点，右下角为终点，那么机器人只能往右或往下走，因此到达终点的路径只能是从上方的格子或左边的格子过来的。设 $dp[i][j]$ 表示从起点到网格中第 $i$ 行第 $j$ 列格子的不同路径数，则有状态转移方程：

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

边界条件为 $dp[0][j] = 1$ 和 $dp[i][0] = 1$，因为从起点出发到达第一行和第一列的任意格子只有一种路径。最终结果为 $dp[m-1][n-1]$。

以下是 C++ 代码实现：

int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1)); // 初始化为1
    for(int i = 1; i < m; i++) {
        for(int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-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 迷宫的左上角 ，迷宫中每个格子中有距离数值，机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角的最小距离和最短路径

的位置。请设计一个算法帮助机器人找到最小距离和最短路径。

算法思路：

1. 初始化一个 m x n 的二维数组 dp，dp[i][j] 表示从起点到网格位置 (i,j) 的最小距离和。

2. 由于机器人只能向下或向右移动，所以起点到第一行和第一列的最小距离和就是逐个加上对应的格子的距离值。

3. 对于其他位置 (i,j)，机器人只能从上面或左边的格子到达，所以可以得到状态转移方程：

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

其中，grid[i][j] 表示网格位置 (i,j) 的距离值。

4. 最终的最小距离和就是 dp[m-1][n-1]，同时，可以根据 dp 数组回溯出最短路径。

具体实现：

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};