题目描述

[EN | CN]

一个机器人位于一个 $m \times n$ 网格的左上角。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径?

示例 1:

1
2
3
4
5
6
7
8
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

1
2
输入: m = 7, n = 3
输出: 28

提示:

  • $1 \le m, n \le 100$;
  • 题目数据保证答案小于等于 $2 \times 10^9$。

解法 1:排列组合

机器人一共需要走 $(m + n + 2)$ 步才能从左上角走到右下角,这里面包括了 $(m - 1)$ 步往右走、$(n - 1)$ 步往下走,所以问题的本质是「从 $(m + n - 2)$ 个元素中抽 $(m - 1)$ 个元素的组合」。

复杂度分析略。

实现与结果如下:

1
2
3
4
from math import factorial as f
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return f(m + n - 2) // f(m - 1) // f(n - 1)
  • 执行用时:32 ms,在所有 Python3 提交中击败了 93.92% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 6.25% 的用户。