难度: 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运行时间: 44 ms
内存: 15.3 MB
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
memo = dict()
def dp(i, j):
if i < 0:
return 0
if j < 0:
return 0
if i == 0 and j == 0:
return 1
if (i, j) in memo:
return memo[(i, j)]
res = dp(i-1, j) + dp(i, j-1)
memo[(i, j)] = res
return res
return dp(m-1, n-1)
这个题解使用动态规划的思路来解决问题。定义函数 dp(i, j) 表示从起点走到位置 (i, j) 的不同路径数量。机器人每次只能向下或向右移动，因此到达 (i, j) 的路径数等于到达 (i-1, j) 和 (i, j-1) 的路径数之和。使用记忆化搜索避免重复计算子问题，将已计算过的结果存储在 memo 字典中。边界条件是当 i 或 j 小于0时路径数为0，当到达起点 (0, 0) 时路径数为1。最终返回 dp(m-1, n-1) 即为从起点到终点的不同路径总数。
时间复杂度: O(m*n)
空间复杂度: O(m*n)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
memo = dict()
def dp(i, j):
# 当 i 或 j 小于0时，返回0，表示无法到达
if i < 0:
return 0
if j < 0:
return 0
# 当到达起点 (0, 0) 时，返回1，表示找到一条路径
if i == 0 and j == 0:
return 1
# 如果 (i, j) 的结果已经计算过，直接返回记忆化的值
if (i, j) in memo:
return memo[(i, j)]
# 到达 (i, j) 的路径数等于到达 (i-1, j) 和 (i, j-1) 的路径数之和
res = dp(i-1, j) + dp(i, j-1)
# 将计算结果存入 memo 字典中
memo[(i, j)] = res
return res
# 返回从起点到终点的不同路径总数
return dp(m-1, n-1)
在递归函数中，当(i, j)位置超出网格边界时返回0的原因是，这代表机器人不能进入这些位置，因此这些位置不存在有效的路径到达它们。此设定并不意味着机器人不能往回走，而是根据题目设定，机器人只能向右或向下移动，不允许向左或向上，因此超出边界的位置自然不在考虑范围内。
当机器人到达起点(0, 0)时，路径数为1是因为起点是路径的开始点，且只存在一种方式在起点上开始路径——即站在起点上。这是由题目定义决定的，因为所有的路径都从此点出发。在这个问题的设定中，不存在其他情况使得起点路径数不为1，因为起点总是固定的，且机器人总是从这一点开始移动。
对于非常大的网格尺寸，我们可以考虑以下几种优化策略：1. 使用迭代而非递归方法，通过迭代计算动态规划表，避免递归的深度限制和栈溢出的问题。2. 采用空间优化技术，例如只存储动态规划表中的当前行和前一行，因为计算当前行值只需要前一行的数据。这可以将空间复杂度从O(m*n)降低到O(min(m,n))。3. 如果问题允许，还可以使用并行处理技术，利用多线程或分布式计算来加速整个计算过程。