正文

【LeetCode】63. Unique Paths II 解题报告（Python & C++）

IP云
IP云V管理员/3 阅读
09/30
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

作者： 负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/

题目地址：https://leetcode.com/problems/unique-paths-ii/description/

题目描述：

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

Input:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

题目大意

给出了一个m * n的地图，上面有个机器人位于左上角，现在他想到达右下角。但是这个地图某些位置可能有障碍物。它每次只能向右边或者下边走一步，问能到达右下角的方式有多少种。

解题方法

方法一：记忆化搜索

这个题是62. Unique Paths的翻版，加上了障碍物一项。同样的分析：

到达某个位置的次数怎么计算？可以想到是到达这个位置上面的位置的次数+到达坐标的次数。

注意了，有障碍物！其实有障碍物的话可以直接返回这个点的可能次数是0.为什么？因为每个点能从左或者上边过来，如果某个方向是障碍物的话，那么从障碍物过来的可能性是0.

如果递归到边界以外的话，可能性也是0，这样给第一行或者第一列提供了终止条件。如果是左上角开始的位置，那么方式只有1种，代表了起始条件。

另外使用了记忆化数组保存已经走过位置的次数，可以加快运算。

时间复杂度是O(m * n)，空间复杂度是O(m * n)。这个方法AC了，但是竟然没进排名。。

class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
m, n = len(obstacleGrid), len(obstacleGrid[0])
memo = [[0] * n for _ in range(m)]
return self.dfs(m - 1, n - 1, obstacleGrid, memo) def dfs(self, m, n, obstacleGrid, memo): # methods of postion m, n
if obstacleGrid[m][n] == 1:
return 0
if m < 0 or n < 0:
return 0
if m == n == 0:
return 1
if memo[m][n]:
return memo[m][n]
up = self.dfs(m - 1, n, obstacleGrid, memo)
left = self.dfs(m, n - 1, obstacleGrid, memo)
memo[m][n] = up + left
return memo[m][n]

方法二：动态规划

看到上面记忆化搜索的方法就知道这个题同样可以使用动态规划解决。第一行第一列的所有方式只有1种，到达其他位置的方式是这个位置上面 + 这个位置左边用DP的话，注意需要判断某个位置是不是有障碍物，如果有障碍物，那么到达这个地方的方法是0。总体思路和上面记忆化搜索差不多。

时间复杂度是O(m * n)，空间复杂度是O(m * n)。

动态规划写了三种方法，不停地优化，最后打败了100%的提交。

第一种，就是对上面的记忆化搜索的修改，给整个数组最上面和最左边加了一层边界，其含义是到达这个位置的方法是0，然后这么做的目的是防止下标越界。

这个做法超过了69%的提交。

class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
m, n = len(obstacleGrid), len(obstacleGrid[0])
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if obstacleGrid[i - 1][j - 1] == 1:
dp[i][j] = 0
else:
if i == j == 1:
dp[i][j] = 1
else:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m][n]

上面的方法不好，因为修改了边界之后和原始的地图对应关系被打乱了，很容易出错。所以有了第二个版本，不要添加边界，直接判断是不是到达了最上面一行或者最左边一行，如果不是第一行那么加上上面行的数值，如果不是第一列那么加上第一列的数值。

这个做法打败了100%的提交。

class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
m, n = len(obstacleGrid), len(obstacleGrid[0])
dp = [[0] * n for _ in range(m)]
if obstacleGrid[0][0] == 0:
dp[0][0] = 1
for i in range(m):
for j in range(n):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
if i != 0:
dp[i][j] += dp[i - 1][j]
if j != 0:
dp[i][j] += dp[i][j - 1]
return dp[m - 1][n - 1]

第三个版本，利用Python语言特性来减少判断次数。我们遍历的方向是第一行从左到右，然后再第二行从左到右的方式进行的，这样如果把dp全部初始化成了0，那么当计算第一行的时候dp[-1][j]实际上就是最后一行的dp，也就是0.同样的，dp[i][-1]实际上是最后一列的dp，但是还没遍历到过，所以也是0.总之，虽然dp数组在计算第一行和第一列的时候用到了最后一行最后一列的dp数据，但是由于还没有遍历到，那么dp数组实际上是0，所以完全可以省去判断。这种方式对于C++和Java不能进行负数索引的不能用。

这个做法打败了100%的提交。

class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
m, n = len(obstacleGrid), len(obstacleGrid[0])
dp = [[0] * n for _ in range(m)]
if obstacleGrid[0][0] == 0:
dp[0][0] = 1
for i in range(m):
for j in range(n):
if obstacleGrid[i][j] == 0:
if i == j == 0:
continue
else:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]

上面两个做法可以看出，这个题的规模确实很小，总运行时间只有20ms，就能打败100%。哪怕少了一个判断，就能超出一部分提交。

二刷的时候，使用动态规划，C++代码如下：

class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
const int M = obstacleGrid.size(), N = obstacleGrid[0].size();
vector<vector<int>> dp(M + 1, vector<int>(N + 1, 0));
if (obstacleGrid[0][0] != 1)
dp[1][1] = 1;
for (int i = 1; i < M + 1; ++i) {
for (int j = 1; j < N + 1; ++j) {
if (i == 1 && j == 1) continue;
if (obstacleGrid[i - 1][j - 1] != 1)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[M][N];
}
};

日期

2018 年 10 月 18 日 —— 做梦都在科研
2018 年 12 月 29 日 —— 2018年剩余电量不足1%

【LeetCode】63. Unique Paths II 解题报告（Python & C++）的更多相关文章

  1. LeetCode&colon; Unique Paths II 解题报告

    Unique Paths II Total Accepted: 31019 Total Submissions: 110866My Submissions Question Solution  Fol ...

  2. LeetCode 63&period; Unique Paths II不同路径 II &lpar;C&plus;&plus;&sol;Java&rpar;

    题目: A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). ...

  3. &lbrack;LeetCode&rsqb; 63&period; Unique Paths II 不同的路径之二

    A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The ...

  4. leetcode 63&period; Unique Paths II

    Follow up for "Unique Paths": Now consider if some obstacles are added to the grids. How m ...

  5. LeetCode&colon; 63&period; Unique Paths II（Medium）

    1. 原题链接 https://leetcode.com/problems/unique-paths-ii/description/

  6. &lbrack;leetcode&rsqb; 63&period; Unique Paths II &lpar;medium&rpar;

    原题 思路: 用到dp的思想,到row,col点路径数量 : path[row][col]=path[row][col-1]+path[row-1][col]; 遍历row*col,如果map[row ...

  7. leetcode 62&period; Unique Paths 、63&period; Unique Paths II

    62. Unique Paths class Solution { public: int uniquePaths(int m, int n) { || n <= ) ; vector<v ...

  8. 【LeetCode】63&period; Unique Paths II

    Unique Paths II Follow up for "Unique Paths": Now consider if some obstacles are added to ...

  9. &lbrack;Leetcode Week12&rsqb;Unique Paths II

    Unique Paths II 题解 原创文章,拒绝转载 题目来源:https://leetcode.com/problems/unique-paths-ii/description/ Descrip ...

随机推荐

  1. 【原】Gradle调用shell脚本和python脚本并传参

    最近由于项目自动化构建的需要,研究了下gradle调用脚本并传参的用法,在此作个总结. Pre build.gradle中定义了$jenkinsJobName $jenkinsBuild两个Jenki ...

  2. 2 配置Ionic开发环境以及创建新的项目

    1.开发环境需要的软件有: node.js http://nodejs.org  可以到官方网站下载对应平台的安装包安装即可,如果已经安装,需要把它升级到最新的稳定版本   在终端可以输入$node ...

  3. &lbrack;WinAPI&rsqb; API 8 &lbrack;获取磁盘空间信息&rsqb;

    获取磁盘分区的总容量和空闲空间的容量可以使用GetDiskFreeSpace函数或GetDiskFree SpaceEx函数.GetDiskFreeSpace使用DWORD类型作为输出参数,由于DWO ...

  4. 【POJ 2104】 K-th Number 主席树模板题

    达神主席树讲解传送门:http://blog.csdn.net/dad3zz/article/details/50638026 2016-02-23:真的是模板题诶,主席树模板水过.今天新校网不好,没 ...

  5. &lbrack;转&rsqb;Maintain File Upload Control on Postbacks

    本文转自:http://www.ironspeed.com/articles/Maintain%20File%20Upload%20Control/Article.aspx Introduction ...

  6. HDU 5009 DP

    2014 ACM/ICPC Asia Regional Xi'an Online 对于N个数 n(1 ≤ n ≤ 5×104), 把N个数分成随意个区间,每一个区间的值是该区间内不同数字个数的平方和, ...

  7. 感知机和线性单元的C&num;版本

    本文的原版Python代码参考了以下文章: 零基础入门深度学习(1) - 感知器 零基础入门深度学习(2) - 线性单元和梯度下降 在机器学习如火如荼的时代,Python大行其道,几乎所有的机器学习的 ...

  8. Spring事务&commat;Transactional标签深入学习

    事务管理是应用系统开发中必不可少的一部分.Spring为事务管理提供了丰富的功能支持.Spring事务管理分为编码式和声明式 两种方式.编码式事务指的是通过编码方式实现事务;声明式事务基于AOP,将具 ...

  9. xshell远程终端操作Ubuntu server安装LAMP环境之最详细笔记之二PHP开发环境配置

    前言: 昨天学会了安装server,今天试着通过远程终端xshell来安装LAMP,搭配一下开发环境,也有集成环境可以一键安装使用,还是瞎折腾一下,手动一步一步搭建一下这个开发环境. 接上一篇:ubu ...

  10. Unirest－拼装http请求发送rest接口

    public static Integer getInfo(String name) { HttpResponse<Integer> httpResponse = null; try { ...