有一个n*m的矩阵迷宫，每个点都可以走，如果从1,1点出发，只能向下或者向右行走，请问走到n,m点有多少种不同的方法。

这个问题可以使用动态规划来解决。

我们可以定义一个二维数组dp，其中dp[i][j]表示从起点(1,1)到达(i,j)的不同路径数。显然，dp[1][1]=1，因为起点只有一种走法，即不动。

对于任意一个位置 (i, j)，我们可以从上面的位置 (i-1, j) 或者左边的位置 (i, j-1) 走过来。因此，到达当前位置的不同路径数等于到达上面位置的路径数加上到达左边位置的路径数，即：

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

最后，dp[n][m]即为从起点到达终点的不同路径数。

以下是Python代码实现：

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

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

相关问题

用c++完成这道题：有一个 n \times mn×m 的矩阵迷宫，每个点都可以走，如果从 1,11,1 点出发，只能向下或者向右行走，请问走到 n,mn,m 点有多少种不同的方法。

以下是用动态规划（Dynamic Programming）的方法来解决这个问题。

首先，我们可以定义一个二维数组 dp，其中 dp[i][j] 表示从起点 (1, 1) 走到 (i, j) 的不同路径数。因为从起点出发只能向下或者向右走，所以我们可以得到状态转移方程：

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

其中 dp[i-1][j] 表示从 (1, 1) 走到 (i-1, j) 的路径数，dp[i][j-1] 表示从 (1, 1) 走到 (i, j-1) 的路径数。因为只能向下或者向右走，所以从 (1, 1) 走到 (i, j) 的不同路径数就是这两个值的和。

最后，我们只需要初始化 dp[1][1] = 1，然后按照上述状态转移方程来计算 dp[n][m] 即可。

下面是完整的 C++ 代码实现：

#include <iostream>
#include <vector>

using namespace std;

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

int main() {
    int m, n;
    cout << "请输入矩阵的行数和列数：";
    cin >> n >> m;
    cout << "从起点 (1, 1) 走到终点 (" << n << ", " << m << ") 的不同路径数为：" << uniquePaths(m, n) << endl;
    return 0;
}

请用c++写一段代码：给定一个m行n列的迷宫，迷宫中每个格子中有距离数值，一个机器人只能向下和向右移动，求机器人从左上角到右下角的最短距离和最短路径

假设迷宫的距离数值矩阵为maze，m行n列，机器人从左上角出发，到达右下角的最短距离和最短路径可以使用动态规划算法解决。

具体思路如下：

1. 初始化一个m行n列的二维数组dp，用来存储每个位置到达左上角的最短距离。

2. 初始化dp[0][0]为maze[0][0]，因为机器人从左上角出发，所以到达左上角的最短距离就是左上角的距离数值。

3. 对于第一行和第一列的位置，因为只能向右或向下移动，所以到达这些位置的最短距离就是前一个位置的最短距离加上当前位置的距离数值。

4. 对于其他位置，到达当前位置的最短距离就是从上面或左边的位置中选择一个最小值，再加上当前位置的距离数值。

5. 最后dp[m-1][n-1]就是机器人从左上角到达右下角的最短距离，可以使用回溯算法找出最短路径。

代码如下：

#include <stdio.h>

#define MAX_M 100
#define MAX_N 100

int maze[MAX_M][MAX_N]; // 迷宫距离数值矩阵
int dp[MAX_M][MAX_N];   // 到达每个位置的最短距离

int min(int a, int b) { return a < b ? a : b; }

int main()
{
    int m, n;
    printf("请输入迷宫的行数和列数：");
    scanf("%d %d", &m, &n);

    printf("请输入迷宫中每个格子的距离数值：\n");
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &maze[i][j]);
        }
    }

    // 初始化dp数组
    dp[0][0] = maze[0][0];
    for (int i = 1; i < m; i++)
    {
        dp[i][0] = dp[i-1][0] + maze[i][0];
    }
    for (int j = 1; j < n; j++)
    {
        dp[0][j] = dp[0][j-1] + maze[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]) + maze[i][j];
        }
    }

    printf("机器人从左上角到达右下角的最短距离为：%d\n", dp[m-1][n-1]);

    // 回溯算法求解最短路径
    int x = m - 1, y = n - 1;
    while (x != 0 || y != 0)
    {
        printf("(%d,%d) ", x, y);
        if (x == 0)
        {
            y--;
        }
        else if (y == 0)
        {
            x--;
        }
        else
        {
            if (dp[x-1][y] < dp[x][y-1])
            {
                x--;
            }
            else
            {
                y--;
            }
        }
    }
    printf("(0,0)\n");

    return 0;
}