我要招人

去企业版

首页 > 试题广场 >

不同路径的数目(一)

[编程题]不同路径的数目(一)

热度指数：102686 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

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

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

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

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

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

示例1

输入

2,1

输出

示例2

输入

2,2

输出

算法知识视频讲解

蒙牛麦片

发表于 2021-07-16 18:14:21

精华题解 NC34 求路径题意分析：算出从起点到终点的路径数目。题解一（动态规划）：假设机器人站在点(i，j)处，其可以从(i-1，j)向下移动一行走到，也可以从向右移动一步走到。因此到达位置(i，j)出路径的数目等于到达位置(i-1，j)的路径数目与达到(i，j-1)的路径数目之和。我们假设dp[ 展开全文

LaN666

发表于 2021-07-16 17:50:25

精华题解 NC34 求路径题目思路：这道题目其实很一道很经典的动态规划题目，题目意思很好理解，就是找从起点到终点的所有可行的路径。约束的两个条件：机器人每次只能往右或者往下走机器人不能越界我们看到这张图就明白一切：方法一：经典使用dp数组有了上面的两个条件，我们就可以解决这个题目了。展开全文

牛客题解官

发表于 2022-04-22 12:41:44

精华题解题目主要信息：给定一个m∗nm*nm∗n的矩阵，要求从矩阵的左上角走到右下角的不同路径数量每次只能往下或者往右走举一反三：学习完本题的思路你可以解决如下题目： BM68.矩阵的最小路径和方法一：递归(推荐使用) 知识点：递归递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一展开全文

未来0116

发表于 2021-07-10 09:09:11

精华题解一.题目描述：NC34求路径题目链接：https://blog.nowcoder.net/detail/0?qurl=/practice/166eaff8439d4cd898e3ba933fbc6358一个机器人在m×n大小的地图的左上角（起点），机器人每次向下或者向右移动，机器人要到达地图的右下角展开全文

漫漫云天自翱翔

发表于 2021-07-18 20:20:27

精华题解题解一：动态规划题解思路： dp[i][j]代表从起点到(i,j)的路径数量,到(i,j)只能从(i-1,j)和(i,j-1)到达。所以dp[i][j] = dp[i-1][j]+dp[i][j-1]; 图示：54 dp数组变化*复杂度分析：** 时间复杂度：O(MN) 展开全文

王清楚

发表于 2020-12-11 11:46:47

一个机器人在m×n大小的地图的左上角（起点）。机器人每次向下或向右移动。机器人要到达地图的右下角（终点）。可以有多少种不同的路径从起点走到终点？首先，我们可以发现第一行和第一列的位置只能有一种方法到达对于其它位置来说，到达这个位置有两种情况：一种是从上面的格子走过来的另一种是从左边的格子走过来的所以展开全文

华科不平凡

发表于 2020-08-30 21:01:50

dp[i][j]表示前i行、j列的路径数，状态公式如下：如果i >= 2 && j >= 2，那么dp[i][j] = dp[i-1][j] + dp[i][j-1] dp[1][k] = 1 dp[k][1] = 1 解释如下：当列数和行数大于2的时候，当前节展开全文

不知道要取什么昵称

发表于 2021-10-29 19:04:28

#我提供此题的第二种写法，动态规划前面有人讲解就不说了，用python写，真的简单太多了。这里一定要导入math包，主要是调用math.factorial import math class Solution: def uniquePaths(self , m , n ): 展开全文

Stackingrule

发表于 2020-10-14 23:02:26

求路径需要用动态规划 Dynamic Programming 来解，可以维护一个二维数组 dp，其中 dp[i][j] 表示到当前位置不同的走法的个数，然后可以得到状态转移方程为: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，这里为了节省空间，使用一维数组 dp 展开全文

等一个广哥哥

发表于 2021-05-17 10:35:30

求路径---动态规划当然了，左上角的格子到达方式只有一个，第一行的到达方式只有左边的格子向右走，第一列的到达方式只有上一行的格子想下走，分析清楚情况根据实际情况写代码即可。 class Solution { public: int uniquePaths(int m, int n) { 展开全文

铁箫人语csk

发表于 2022-02-12 00:18:23

题目: NC34 求路径如图,把旧起点转换成新起点,4×3网格变为3×2网格,由数学知识易知: 答案为:(23+2)\tbinom{2}{3+2}(3+22)即(25)\tbinom{2}{5}(52) 即:(5!/(5-2)!) / (2!),由此,如下计算: import java.ut 展开全文