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

1.题目描述

描述

一个机器人在m×n大小的地图的左上角（起点）。

机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。

可以有多少种不同的路径从起点走到终点？

备注：m和n小于等于100,并保证计算结果在int范围内

数据范围：0 < n,m \le 1000<n,m≤100，保证计算结果在32位整型范围内

要求：空间复杂度 O(nm)O(nm)，时间复杂度 O(nm)O(nm)

进阶：空间复杂度 O(1)O(1)，时间复杂度 O(min(n,m))O(min(n,m))

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

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

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

从( m − 1 , n ) (m-1,n)(m−1,n)点向下走一步

从( m , n − 1 ) (m,n-1)(m,n−1)点向右走一步

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

时间复杂度为o ( m + n ) o(m+n)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);
    }

思路二：组合数

代码实现

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.运行结果

成功通过！