如何求解M×N网格中机器人的唯一路径数？

嘿，我来帮你搞定这个机器人找路径的问题～ 首先咱们明确下核心需求：机器人在m行n列网格的左上角，每次只能向下或向右移动，求到达右下角的唯一路径总数。你的递归+记忆化思路完全没问题，我来帮你补全代码，再拓展几种更实用的解法。

你的递归+记忆化代码修正与解释 #

你的代码框架已经很对了，就是没写完递归调用的参数，还有可以优化下缓存键的写法（避免字符串拼接的潜在冲突）。下面是修正后的完整版本：

def paths(m, n, a, b, memo):
    # 网格为空或当前位置超出边界，路径数为0
    if a == 0 or b == 0 or m > a or n > b:
        return 0
    # 到达终点，返回1条有效路径
    if m == a and n == b:
        return 1
    # 用元组当缓存键，比字符串拼接更安全（比如避免m=12,n=3和m=1,n=23的键冲突）
    key = (m, n)
    if key in memo:
        return memo[key]
    # 递归计算：当前路径数 = 向下走一步的路径数 + 向右走一步的路径数
    memo[key] = paths(m + 1, n, a, b, memo) + paths(m, n + 1, a, b, memo)
    return memo[key]

# 调用示例：3行3列网格，起点(1,1)，终点(3,3)
print(paths(1, 1, 3, 3, {}))  # 输出6，符合预期

关键细节说明： #

• 记忆化缓存：用元组(m,n)作为缓存键，比字符串拼接更可靠，不会出现不同坐标生成相同键的情况。
• 边界逻辑：合并了网格为空和位置越界的判断，让代码更简洁。
• 递归分解：完全贴合问题规则——每一步只有两个选择，所以当前位置的路径数是两个方向路径数的总和。

更直观的递归写法（调整坐标体系） #

如果把起点设为(0,0)，终点设为(m-1,n-1)（更符合编程里的数组索引习惯），代码会更易懂：

def uniquePaths(m, n, memo=None):
    # 初始化缓存，避免每次调用都传空字典
    if memo is None:
        memo = {}
    # 到达起点（递归到最底层，只有1条路径）
    if m == 1 and n == 1:
        return 1
    # 超出网格边界，路径数为0
    if m < 1 or n < 1:
        return 0
    key = (m, n)
    if key in memo:
        return memo[key]
    # 路径数 = 上方格子的路径数 + 左方格子的路径数
    memo[key] = uniquePaths(m-1, n, memo) + uniquePaths(m, n-1, memo)
    return memo[key]

# 调用示例：3行3列网格
print(uniquePaths(3, 3))  # 输出6

迭代动态规划解法（避免递归栈溢出） #

如果网格很大（比如m、n都超过100），递归可能会触发栈溢出，这时候用迭代的动态规划更稳定：

def uniquePaths(m, n):
    # 创建dp数组，dp[i][j]表示到(i,j)的路径数
    dp = [[1]*n for _ in range(m)]
    # 第一行和第一列都只有1条路径（只能一直向右/向下走）
    # 填充其他位置：当前路径数 = 上方路径数 + 左方路径数
    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]

print(uniquePaths(3, 3))  # 输出6

数学公式解法（最优效率） #

其实这个问题可以用组合数学直接算：从左上角到右下角，总共要走(m-1)+(n-1)步，其中m-1步向下，n-1步向右。路径数就是从总步数里选m-1步向下的组合数，公式为：

$$C(m+n-2, m-1) = \frac{(m+n-2)!}{(m-1)! \times (n-1)!}$$

对应代码（Python3.10+支持math.comb）：

import math

def uniquePaths(m, n):
    return math.comb(m + n - 2, m - 1)

print(uniquePaths(3, 3))  # 输出6

这个方法时间复杂度O(1)、空间复杂度O(1)，是效率最高的解法。

内容的提问来源于stack exchange，提问作者Utkarsh Prakash