Python给定m行和n列网格，有一个机器人从左上角(0,0)出发，每一步可以向下或向右走一步，问多少种不同的方式走到右下角？

这道题可以使用动态规划来解决。我们可以定义一个二维数组 `dp`，其中 `dp[i][j]` 表示从左上角走到网格 `(i,j)` 的不同路径数。

对于每个格子 `(i,j)`，它可以从它的上方格子 `(i-1,j)` 或者左边格子 `(i,j-1)` 走过来，因此到达当前格子的路径数为到达上方格子和左边格子的路径数之和。即：

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

需要注意的是，对于第一行和第一列的格子，它们只能从左边或上边走过来，因此它们的路径数都为 1。

最终，`dp[m-1][n-1]` 就是从左上角到右下角的不同路径数。

下面是 Python 代码实现：

def uniquePaths(m: int, n: int) -> int:
    # 初始化 dp 数组
    dp = [[0] * n for _ in range(m)]
    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1

    # 填充 dp 数组
    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)$。

相关问题

给定m行和n列网格，有一个机器人从左上角(0,0)出发，每一步可以向下或向右走一步，问多少种不同的方式走到右下角？（请写出Python程序

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

定义一个二维数组dp[i][j]表示到达第i行第j列的格子时的不同走法数量。

由于机器人只能向下或向右走，所以到达dp[i][j]的格子只能从dp[i-1][j]或dp[i][j-1]两个格子走过来。

因此，状态转移方程为：

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

边界条件为：

dp[0][0] = 1

dp[0][j] = 1 (0 ≤ j ≤ n-1)

dp[i][0] = 1 (0 ≤ i ≤ m-1)

最终答案为dp[m-1][n-1]。

下面是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]

测试：

输入：m = 3, n = 7

输出：28