Leetcode 62.不同路径

题目描述：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

1
2

输入：m = 3, n = 7
输出：28

示例 2：

1
2
3
4
5
6
7

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

1
2

输入：m = 7, n = 3
输出：28

示例 4：

1
2

输入：m = 3, n = 3
输出：6

提示：

• $1 <= m, n <= 100$
• 题目数据保证答案小于等于 $2*10^9$

链接：

https://leetcode-cn.com/problems/unique-paths

题目分析

  这是一道很经典的数学题。机器人处在 m x n 的网格中，并且只能往右和往下移动，则从左上角移动到右下角，总的移动路程是一定的，一定是往右走了 n-1 步，往下走了 m-1 步，也即总的移动路程是 m-1+n-1。而不同的移动方案，也即是在 m-1+n-1 步中，选择其中的 m-1 往下（或者选择 n-1 步往右），也即是一个数学组合问题。答案就是 $\binom{m-1+n-1}{m-1}$ 或 $\binom{m-1+n-1}{n-1}$。为了减少运算量，我们可以选择 m 和 n 其中更小的那个来计算。
  虽然题目中保证答案小于等于 $2*10^9$，也即答案不会超过 int 的范围，但是在计算的过程还是会超过，需要使用 long long int 类型。

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long int result = 1;
        for(int i = 1; i < min(m, n); i++){
            result *= (m+n)-i-1;
            result /= i;
        }
        return result;
    }
};

  时间复杂度：$O(\min(m,n))$，其中 $m、n$ 分别是网格的行数和列数。也即计算组合数的时间复杂度。
  空间复杂度：$O(1)$。我们只需要常数的空间存放变量。