【牛客刷题-算法】NC34 不同路径的数目(一) | 动态规划、组合数解法

个人主页-CSDN：清风莫追

🔥 该专栏作为刷题笔记，持续更新中。

推荐一款面试、刷题神器牛客网：👉开始刷题学习👈

---

1.题目描述

描述
一个机器人在m×n大小的地图的左上角（起点）。
机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？

备注：m和n小于等于100,并保证计算结果在int范围内
数据范围：0 < n,m \le 1000 要求：空间复杂度 O(nm)O(nm)，时间复杂度 O(nm)O(nm)
进阶：空间复杂度 O(1)O(1)，时间复杂度 O(min(n,m))O(min(n,m))

2.算法设计思路与代码实现

思路一：动态规划，递归实现

只需明白一件事，因为机器人只能向右或向下走，那么我们要到达$(m,n)$点，有两种方式：

1. 从$(m-1,n)$点向下走一步
2. 从$(m,n-1)$点向右走一步

则从起点到达$(m,n)$点的路径数，就等于从起点到达$(m-1,n)$的路径数与到达$(m,n-1)$的路径数之和。

时间复杂度为$o(m+n)$

代码实现

	int uniquePaths(int m, int n) {
        if(m == 1 || n == 1)
        {
            return 1;
        }
        return uniquePaths(m-1, n) + uniquePaths(m, n-1);
    }

思路二：组合数

对于$m\ast n$的地图，从左上角到右下角一共需要走$m+n-2$步，其中$m-1$步向下，$n-1$步向右。那么这$m+n-2$步中哪些步是向下、哪些是向右呢？这就变成了一个组合问题。

我们只需计算$C_{m+n-2}^{m-1}$的值即可（也可求$C_{m+n-2}^{n-1}$，它们是相等的）。

代码实现

    int uniquePaths(int m, int n) {
        int all = m + n -2;
        int min = m < n ? m : n;
        long long result = 1;
        for(int a = 1, b = min; b <= all; a++, b++){
            result = result * b / a;
        }
        return result;
    }

注意细节

代码中变量result的类型为long long，而题目中提到了路径数不会超过32位的int。那为什么要用long long？这其实也是一个常见的问题，虽然运算结果本身不会溢出，但是仍然需要小心运算过程中的中间结果发生溢出。

例如代码中，result = result * b / a;是先进行乘法运算然后进行除法运算的，可能在做乘法时就已经溢出了。

一个疑惑

代码可以通过牛客的测试集，但是我对循环中的这一语句感到疑惑：result = result * b / a;。它涉及到除法运算，如何保证不会出现不能整除的情况呢？然而在我有限的尝试中，它确实没出现问题。

3.运行结果

成功通过！

---

CSDN话题挑战赛第2期
参赛话题：学习笔记