不同路径的数目(二)

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

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

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

机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？

起点(1)	1	1
1	0	1
1	1	终点(1)

其中，1表示可以行走，0表示不能行走

保证答案在 $int$ 范围内

$1\leq n,m \leq 100$

示例1

输入

[[1,1,1],[1,0,1],[1,1,1]]

输出

说明

从左上角到右下角一共有2条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例2

输入

[[1,0,1]]

输出

说明

从左上角到右下角没有路径可以到达

算法知识视频讲解

牛客504474094号

发表于 2022-04-01 19:21:14

这题是根据不同路径的数目（一）演变而来，使用动态规划解法。不同路径的数目（一）的解法题目描述：有一个m*n矩阵，人只能向右走或向下走。从起点start，到终点end，共有多少条路径？动态解法确定dp数组及下标的含义 dp[i][j] 表示走到矩阵下标[i][j]时，最多的路径。展开全文

猪猪向前冲

发表于 2022-03-20 22:18:34

public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param obstacleGrid int整型vector<vector<>> * @retur 展开全文

牛客327297870号

发表于 2023-04-16 15:16:27

牛客有毒啊，一样的代码，一样的用例，在本地pycharm运行答案正确，牛客运行答案错误。。。而且那测试用例是什么鬼，不是输入数组不是0就是1吗？整一堆A是几个意思。。。 class Solution: def uniquePathsWithObstacles(self , obstacleG 展开全文

姐姐的遮阳伞

发表于 2022-04-10 15:29:11

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param obstacleGrid int整型Array 展开全文

佛说wh

发表于 2022-09-06 16:04:55

2022.0906算法第56题不同路径的数目(二) 这道题对于做过不同路径的数目一，思路还是能够想到的主要就是需要注意两点 1、初始化的时候，如果遇到障碍0的时候，0后面的数据都没法到达，需要赋值为0 2、当状态矩阵在进行递推时，如果遇到障碍0，则直接将该位置赋值为0，其余展开全文

lv98

发表于 2022-08-08 17:38:22

动态规划问题，与没有障碍物的区别在于，初始化时第一行第一列遇到障碍物时，此处以及后面的dp都为0.且递推时，遇到障碍物dp为0，其他仍然按照dp[i][j]=dp[i-1][j]+dp[i][j-1]的递推关系进行。 function uniquePathsWithObstacles( obstac 展开全文