LeetCode(63):不同路径 II
发布日期:2021-08-17 17:17:07 浏览次数:11 分类:技术文章

本文共 2067 字,大约阅读时间需要 6 分钟。

Medium!

题目描述:

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明:m 和 的值均不超过 100。

示例 1:

输入:[  [0,0,0],  [0,1,0],  [0,0,0]]输出: 2解释:3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径:1. 向右 -> 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右 -> 向右

解题思路:

这道题是之前那道 的延伸,在路径中加了一些障碍物,还是用动态规划Dynamic Programming来解,不同的是当遇到为1的点,将该位置的dp数组中的值清零,其余和之前那道题并没有什么区别。

C++解法一:

1 class Solution { 2 public: 3     int uniquePathsWithObstacles(vector
>& obstacleGrid) { 4 if (obstacleGrid.empty() || obstacleGrid[0].empty() || obstacleGrid[0][0] == 1) return 0; 5 vector
> dp(obstacleGrid.size(), vector
(obstacleGrid[0].size(), 0)); 6 for (int i = 0; i < obstacleGrid.size(); ++i) { 7 for (int j = 0; j < obstacleGrid[i].size(); ++j) { 8 if (obstacleGrid[i][j] == 1) dp[i][j] = 0; 9 else if (i == 0 && j == 0) dp[i][j] = 1;10 else if (i == 0 && j > 0) dp[i][j] = dp[i][j - 1];11 else if (i > 0 && j == 0) dp[i][j] = dp[i - 1][j];12 else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];13 }14 }15 return dp.back().back();16 }17 };

或者我们也可以使用一维dp数组来解,省一些空间。

C++解法二:

1 // DP 2 class Solution { 3 public: 4     int uniquePathsWithObstacles(vector
> &obstacleGrid) { 5 if (obstacleGrid.empty() || obstacleGrid[0].empty()) return 0; 6 int m = obstacleGrid.size(), n = obstacleGrid[0].size(); 7 if (obstacleGrid[0][0] == 1) return 0; 8 vector
dp(n, 0); 9 dp[0] = 1;10 for (int i = 0; i < m; ++i) {11 for (int j = 0; j < n; ++j) {12 if (obstacleGrid[i][j] == 1) dp[j] = 0;13 else if (j > 0) dp[j] += dp[j - 1];14 }15 }16 return dp[n - 1];17 }18 };

 

转载于:https://www.cnblogs.com/ariel-dreamland/p/9149807.html

转载地址:https://blog.csdn.net/weixin_30856725/article/details/98794509 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:codeforces 922F Divisibility 构造
下一篇:linux c scanf()小解

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年02月28日 15时10分56秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

python信号采集代码_13行代码实现:Python实时视频采集(附源码) 2019-04-21
h5引入json_纯js直接引入json文件 2019-04-21
python格式化字符串总结_Python字符串处理方法总结 2019-04-21
python中true什么意思_python中的bool是什么意思 2019-04-21
jacobian 矩阵意义_Jacobian矩阵和Hessian矩阵的作用是什么? 2019-04-21
c++ jna 数据类型_JNA 使用总结 2019-04-21
python中如何遍历列表并将列表值赋予_python中如何实现遍历整个列表? 2019-04-21
apache php mysql架构图_Apache+PHP+MYSQL+Tomcat+JK架构设计技巧与应用实战 2019-04-21
xlnt库如何编译_最新mysql数据库源码编译安装。 2019-04-21
mysql 2003错误 10055_MYSQL无法连接---提示10055错误 2019-04-21
mysql redis缓存层_redis实现缓存的两种方式 2019-04-21
git 改local branch名字_用Git管理Latex写论文的工作流程 2019-04-21
mysql索引篇_MySQL索引篇 2019-04-21
有至少一个用MySQL_Mysql有用的面试题 2019-04-21
mysql select同时update_MySQLSELECT同时UPDATE同一张表 2019-04-21
mysql删除后数据库没变化_mysql之delete删除记录后数据库大小不变 2019-04-21
net mysql start3534_MySQL 5.7.14 net start mysql 服务无法启动-“NET HELPMSG 3534” 的奇怪问题... 2019-04-21
pta两个有序链表的合并_7-1 两个有序链表序列的合并 (20分) --- 内存问题再叙 2019-04-21
python问题描述怎么写_python写文件有时候写不进去怎么办 2019-04-21
qpython3安装lxml_在python的lxml中使用xml目录? 2019-04-21