难度: Medium
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7 输出：28
示例 2：
输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3 输出：28
示例 4：
输入：m = 3, n = 3 输出：6
提示：
1 <= m, n <= 1002 * 109注意：本题与主站 62 题相同： https://leetcode-cn.com/problems/unique-paths/
运行时间: 19 ms
内存: 16.0 MB
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# m行n列
dp = [[0] * n] * m
for i in range(m):
for j in range(n):
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
该题解采用动态规划的方法解决问题。首先，定义一个二维数组 dp，其中 dp[i][j] 表示到达网格中第 i 行第 j 列的不同路径数量。初始化 dp 数组时，所有在第一行或第一列的位置只有一种方式到达，即全部向右或全部向下，因此将这些位置的值初始化为 1。对于其他位置 (i, j)，机器人可以从左边 (i, j-1) 或上边 (i-1, j) 的单元格移动过来，因此 dp[i][j] 的值由这两种可能的位置的路径数之和决定，即 dp[i][j] = dp[i-1][j] + dp[i][j-1]。最终，dp数组的最后一个元素 dp[m-1][n-1] 即为所求答案。
时间复杂度: O(m * n)
空间复杂度: O(m * n)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# 初始化一个 m x n 的 dp 数组，所有值为 0
dp = [[0] * n for _ in range(m)] # 使用列表推导式以避免引用相同对象
for i in range(m):
for j in range(n):
if i == 0 or j == 0:
# 第一行或第一列的单元格，只有一条路径
dp[i][j] = 1
else:
# 计算到达当前单元格的路径数量
dp[i][j] = dp[i-1][j] + dp[i][j-1]
# 返回到达最右下角单元格的路径总数
return dp[m-1][n-1]
在动态规划算法中，将第一行和第一列的单元格初始化为 1 是因为每个这样的单元格只能通过一个方向到达：第一行的单元格只能从左边水平移动到达，而第一列的单元格只能从上面垂直移动到达。没有其他路径可以到达这些单元格，因此每个单元格的路径数为 1。这与网格的边界条件密切相关，因为边界单元格标志着从起点到这些单元格的路径选择受到限制（即只有一种选择），进而确保我们的动态规划状态转移方程正确地从边界开始构建解决方案。
动态规划中的更新公式`dp[i][j] = dp[i-1][j] + dp[i][j-1]`确保不遗漏任何可能的路径，因为它考虑了到达当前单元格 (i, j) 的所有可能情况。这个公式表示机器人可以从单元格 (i-1, j)（即当前单元格的上方）或从单元格 (i, j-1)（即当前单元格的左侧）到达 (i, j)。因此，当前单元格的路径总数是从这两个相邻单元格到达的路径数的总和。这个公式基于网格移动的规则（只能向右或向下移动），确保每个单元格的路径计数都是全面且准确的，覆盖了从起点到任何特定单元格的所有可能路径。
在 Python 中，使用列表推导式创建 dp 数组而不是直接分配一个固定值的二维列表，可以避免多个列表间的引用问题。如果直接使用类似 `[[0]*n]*m` 的方法，这将导致所有行引用同一个内部列表对象，从而使得一行中的改动会影响到其他所有行。通过使用列表推导式 `[ [0] * n for _ in range(m) ]`，每一行都会创建一个新的独立列表，这样修改一个单元格的值不会意外地影响到其他行。这在动态规划中是非常重要的，因为我们需要保证在填充 dp 数组时，各行是独立且正确反映各自计算状态的。