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

Java光头强 • 2023年2月20日上午8:51 • 后端漫谈 • 阅读 202

文章目录

1.题目描述
2.算法设计思路与代码实现
3.运行结果
结束语：

个人主页-CSDN：清风莫追

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

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

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, n)$ 点的路径数，就等于从起点到达

(

−

)

(m-1,n)

$(m - 1, n)$ 的路径数与到达

(

−

)

(m,n-1)

$(m, n - 1)$ 的路径数之和。

时间复杂度为

(

)

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);
    }

思路二：组合数

对于

∗

m*n

$m * n$ 的地图，从左上角到右下角一共需要走

−

m+n-2

$m + n - 2$ 步，其中

−

m-1

$m - 1$ 步向下，

−

n-1

$n - 1$ 步向右。那么这

−

m+n-2

$m + n - 2$ 步中哪些步是向下、哪些是向右呢？这就变成了一个组合问题。

我们只需计算

−

C_{m+n-2}^{m-1}

$C_{m + n - 2}^{m - 1}$ 的值即可（也可求

−

C_{m+n-2}^{n-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;
    }